梦破碎的地方，真是太难了.-_-…

三数之和：梦破碎的地方

题目：三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解法-双指针法

思路：

1.
2.
3.

复杂度：

  • 时间复杂度：
  • 空间复杂度：

代码：（成功提交但是有逻辑错误和注释理解错误）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        //计算nums[i] + nums[left] + nums[right] = 0;
        //先对nums[]进行一次排序，方便判断
        sort(nums.begin(),nums.end());
        for(int i = 0;i < nums.size();i++){
            cout << nums[i] << " ";
        }
        cout << endl;
        //遍历数组
        for(int i = 0;i < nums.size();i++){
            //a去重，判断首位元素是否大于0，如果大于0，则三个正数相加不为0
            if(nums[i] > 0){return result;}
            //b去重
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.size()-1;
            //开始收缩
            while(left<right){
                //说明right偏右了
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    //说明left偏左了
                    left++;
                }else if(nums[i] + nums[left] + nums[right]==0){  
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    //去重，如果有的话
                    while(i>0&&nums[left] == nums[left+1]) left++;
                    while(i>0&&nums[right] == nums[right-1]) right--;
                    left++;right--;
                }
                //if(nums[i] + nums[left] + nums[right]==0){
                    // result.push_back({nums[i],nums[left],nums[right]});
                    // //去重，如果有的话
                    // while(i>0&&nums[left] == nums[left+1]) left++;
                    // while(i>0&&nums[right] == nums[right-1]) right--;
                    // left++;right--;
                //}

            }
        }
        return result;
    }
};

int main() {
    Solution solution;
    
    vector<int> nums1 = {-1,0,1,2,-1,-4};
    //vector<vector<int>> expected1 = {{-1, -1, 2}, {-1, 0, 1}};
    vector<vector<int>> result1 = solution.threeSum(nums1);
    //遍历二维数组
    for (int i = 0; i < result1.size(); i++) {
        for (int j = 0; j < result1[i].size(); j++) {
            cout << result1[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

错误描述：

  • if(nums[i] > 0){return result;}这句话不是对a去重，而是判断首位元素是否大于0，如果大于0，则三个正数相加不为0.下一句if(i > 0 && nums[i] == nums[i-1])才是对a去重
  • while(i>0&&nums[left] == nums[left+1]) left++;逻辑错误，应该改为while(left<right && nums[left] == nums[left+1]) left++;,i>0的条件应该不对，虽然通过LeetCode了

代码(更正后)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        //计算nums[i] + nums[left] + nums[right] = 0;
        //先对nums[]进行一次排序，方便判断
        sort(nums.begin(),nums.end());
        for(int i = 0;i < nums.size();i++){
            cout << nums[i] << " ";
        }
        cout << endl;
        //遍历数组
        for(int i = 0;i < nums.size();i++){
            //判断首位元素是否大于0，如果大于0，则三个正数相加不为0
            if(nums[i] > 0){return result;}
            //a去重,如果可以包含重复的三元组，则把这个if语句注释掉,虽然也不太能保留所有重复的三元组
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.size()-1;
            //开始收缩
            while(left<right){
                //说明right偏右了
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    //说明left偏左了
                    left++;
                }else if(nums[i] + nums[left] + nums[right]==0){  
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    //去重，如果有的话
                    //while目的是为了：且不重复的三元组。
                    //如果可以有重复的三元组，则把这两个while注释掉。
                    //实际测试虽然也不太能保留所有重复的三元组，不过应该是left++;right--;同时收缩的缘故
                    while(left<right && nums[left] == nums[left+1])
                    {
                        left++;
                        cout << "left = "<< left << endl;
                    }
                    while(left<right && nums[right] == nums[right-1])
                    {
                        right--;
                        cout << "right = "<< right << endl;
                    }
                    left++;right--;
                }
            }
        }
        return result;
    }
};

语法小计

  1. 该题没有语法小计
    *
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。