1 三数之和

分析

\begin{algorithm} \caption{threeSum(nums)} \begin{algorithmic} \State List[List[int]] result \If{nums.length<3} \State \Return result\Comment{当数组长度不足3时不可能有满足情况的组合} \EndIf \State sort(nums)\Comment{对nums进行排序} \State target=0\Comment{可进行扩展} \For{i=0\To nums.length-2}\Comment{保证有i,j,k的空间} \State j = i + 1 \State k = nums.length - 1 \If{i>0 \And nums[i]==nums[i-1]} \Continue \EndIf \While{j<k}\Comment{遍历i某值下的所有情况} \If{nums[i]+nums[j]+nums[k]<target} \State j = j + 1 \While{nums[j]==nums[j-1]\And j<k} \State j = j + 1 \EndWhile \Elif{nums[i]+nums[j]+nums[k]<target} \State k = k -1 \While{nums[k]==nums[k+1]\And j<k} \State k = k - 1 \EndWhile \Else \State nums.append([nums[i],nums[j],nums[k]]) \State j = j + 1 \State k = k - 1 \While{nums[j]==nums[j-1]\And nums[k]==nums[k+1]\And j<k} \State j = j + 1\Comment{j,k不一起蹦的原因，当更新后落入这个while循环假，设j,k之间仅有一个元素，且这个元素对于j而言是新值，一旦二者同时变动j,k将会同时指向相同的元素而跳出循环，造成缺少含有这个的组合(1,11,15)[(10,11,15)j=10,k=15,i=1]} \EndWhile \EndIf \EndWhile \EndFor \Return result \end{algorithmic} \end{algorithm}

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        if len(nums) < 3:
            return result
        target = 0
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]: continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if (nums[i] +  nums[j] + nums[k] < target):
                    j += 1
                    while nums[j] == nums[j-1] and j < k: j += 1
                elif (nums[i] + nums[j] + nums[k] > target):
                    k -= 1
                    while nums[k] == nums[k+1] and j < k: k -= 1
                else:
                    result.append([nums[i], nums[j], nums[k]])
                    j += 1
                    k -= 1
                    while (nums[j] == nums[j-1] and nums[k] == nums[k+1] and j < k):
                        j += 1
        return result

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if (nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        const int target = 0;
        for (auto i = nums.begin(); i < last - 2; i++){
            auto j = i + 1;
            if (i > nums.begin() && *i == *(i-1)) continue;
            auto k = last - 1;
            while (j < k){
                if (*i + *j + *k < target){
                    j++;
                    while (*j == *(j-1) && j < k) j++;
                }
                else if (*i + *j + *k > target){
                    k--;
                    while (*k == *(k+1) && j < k) k--;
                }
                else {
                    result.push_back({*i, *j, *k});
                    j++;
                    k--;
                    while (*j == *(j-1) && *k==*(k+1) && j < k) j++;
                }
            }
        }
        return result;
    }
};

2 最接近的三数之和

分析

该题较上题而言十分相似，也可以先排序后左右夹逼，但有以下区别：

需要两个记录变量一个记录元素和，另一个记录绝对差
指针的跳动规则也存在不同，当和超过target时k向左跳动，小于则j向右跳动

\begin{algorithm} \caption{ThreeSumClosest(nums, target)} \begin{algorithmic} \State \textbf{输入:} 数组 nums，整数 target \State \textbf{输出:} 最接近 target 的三个整数之和 \State 初始化 closest = $\infty$ \Comment{用于记录当前最接近的差值} \State 初始化 sum\_r = $\infty$ \Comment{用于记录当前最接近的三元组和} \State Sort(nums) \Comment{对数组进行排序，以便使用双指针技巧} \For{$i = 0$ \textbf{到} $len(nums) - 2$} \If{$i > 0$ \textbf{且} $nums[i] == nums[i-1]$} \State \Continue \Comment{跳过重复值，避免重复计算} \EndIf \State 初始化 $j = i + 1$ \Comment{左指针} \State 初始化 $k = len(nums) - 1$ \Comment{右指针} \While{$j < k$} \State 计算 $sum\_i = nums[i] + nums[j] + nums[k]$ \Comment{当前三元组的和} \State 计算 $closest\_i = |sum\_i - target|$ \Comment{当前三元组和与目标值的差值} \If{$closest\_i < closest$} \State 更新 $sum\_r = sum\_i$ \Comment{更新最接近的三元组和} \State 更新 $closest = closest\_i$ \Comment{更新最接近的差值} \EndIf \If{$sum\_i < target$} \State $j = j + 1$ \Comment{如果当前和小于目标值，移动左指针增加和} \Else \State $k = k - 1$ \Comment{如果当前和大于目标值，移动右指针减小和} \EndIf \EndWhile \EndFor \State \Return $sum\_r$ \Comment{返回最接近的三元组和} \end{algorithmic} \end{algorithm}

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        closest_r = float("inf")
        sum_r = float("inf")
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]: continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                sum_i = nums[i] + nums[j] + nums[k]
                closest_i =  abs(sum_i - target)
                if closest_i < closest_r:
                    sum_r = sum_i
                    closest_r = closest_i
                if sum_i < target: j += 1
                else: k -= 1
        return sum_r

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int sum_r = INT_MAX;
        int closest_r = INT_MAX;
        sort(nums.begin(), nums.end());
        auto last = nums.end();
        for (auto i = nums.begin(); i < last - 2; i++){
            if (i > nums.begin() && *i == *(i-1)) continue;
            auto j = i + 1;
            auto k = last - 1;
            while (j < k){
                auto sum_i = *i + *j + *k;
                auto closest_i = abs(sum_i - target);
                if (closest_i < closest_r){
                    closest_r = closest_i;
                    sum_r = sum_i;
                }
                if (sum_i < target) j++;
                else k--;
            }
        }
        return sum_r;
    }
};