极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 如何在数组中找出三个数之和为 N

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 177 (opens new window)

Author

回答者: HNHED (opens new window)

排序之后使用双指针 let ar = [5, 12, 6, 3, 9, 2, 1, 7];

function getthreenum(arr, target, result = []) { arr = arr.sort((a, b) => a - b) const len = arr.length; for (let i = 0; i < len; i++) { let j = i + 1; let k = len - 1; while (j < k) { if (arr[j] + arr[k] > target - arr[i]) { k--; } else if (arr[j] + arr[k] < target - arr[i]) { j++; } else { result.push([arr[i], arr[j], arr[k]]); j++; } } } return result; } console.log(getthreenum(ar, 13, []));

Author

回答者: Zss1990 (opens new window)

可以使用双指针法,注意去重;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        if(nums.empty() || nums.size()<3)
            return ans;

        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size(); i++){
            if(i==0 || (i>0&&nums[i]!=nums[i-1])){
                int left = i+1;
                int right = nums.size()-1;
                while(left<right){
                    int s = nums[i]+nums[left]+nums[right];
                    if(s<0){
                        left++;
                    }else if(s>0) {
                        right--;
                    }else{
                        ans.push_back({nums[i], nums[left], nums[right]});
                        while(left<right && nums[left]==nums[left+1]){  // 找到下一个不相等的下标,为了去重
                            left++;
                        }
                        while(left<right && nums[right]==nums[right-1]){ // 找到下一个不相等的下标,为了去重
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
};

参考:【LeetCode-数组】三数之和 - Flix - 博客园 (opens new window)

Author

回答者: Zss1990 (opens new window)

可以使用双指针法,注意去重;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        if(nums.empty() || nums.size()<3)
            return ans;

        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size(); i++){
            if(i==0 || (i>0&&nums[i]!=nums[i-1])){
                int left = i+1;
                int right = nums.size()-1;
                while(left<right){
                    int s = nums[i]+nums[left]+nums[right];
                    if(s<0){
                        left++;
                    }else if(s>0) {
                        right--;
                    }else{
                        ans.push_back({nums[i], nums[left], nums[right]});
                        while(left<right && nums[left]==nums[left+1]){  // 找到下一个不相等的下标,为了去重
                            left++;
                        }
                        while(left<right && nums[right]==nums[right-1]){ // 找到下一个不相等的下标,为了去重
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
};

参考:【LeetCode-数组】三数之和 - Flix - 博客园 (opens new window)

Last Updated: 11/4/2022, 6:34:31 PM