LeetCode Daily Question 3

Mar 7th 2022

3 月 7 日 每日一题

题目：15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

1
2
eg: Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

思路

这道题的思路很简单，先 sort，再设 pivot，之后用双指针找到两数之和等于-pivot。如果遇到合适的 triplet，需要考虑之后的元素是否和当前的相等以避免重复。最后使用一个 while 来避免 pivot 重复。

1
2
while(i + 1 < nums.size() && nums[i + 1] == nums[i])
    i++;

但是因为 edge case 和一些很蠢的错折磨了很久，写到后面属实有点气急败坏…
几个教训：

  1. a && b 的计算
    先看 a，若 a 是假，则结束，整个表达式的值为假。
    若 a 是真，再看 b，如 b 为假，整个表达式为假。
    若 b 为真，则整个表达式为真。
    所以最后的 while 判断条件如果反过来就会导致[0]这个 case 越界。
  2. 完全没有必要使用指针，两个 int 即可
  3. 关于并列的 if 和 if else 并列区别很大，需要注意。
  4. 不建议使用 for(int i = 1…)这种从 1 开始遍历的写法，很容易想错导致越界访问。并且还是那句话，写之前就想清楚 edge case，最好在纸上列一下。
  5. 最后，气急败坏的状态下建议先做其他事，调整下大脑。

代码

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
    vector<vector<int>> threeSum(vector<int>& nums) {
    std::sort(nums.begin(),nums.end());
    vector<vector<int>> res;
    for(int i = 0; i < nums.size(); i++){
        int left = i + 1;
        int right = nums.size() - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum < -nums[i])
                left++;
            else if(sum > -nums[i])
                right--;
            else{ //else可以避免2 -1 -1
                vector<int> temp = {nums[i], nums[left], nums[right]};
                res.push_back(temp);
                while(left < right && nums[left] == temp[1])
                    left++;
                while(left < right && nums[right] == temp[2])
                    right--;
            }
        }
        while(i + 1 < nums.size() && nums[i + 1] == nums[i])
            i++;
    }
    return res;
}
,
  1. 3 月 7 日 每日一题
    1. 题目：15. 3Sum
    2. 思路
    3. 代码