【題解】LeetCode 15. 3Sum

題目敘述:https://leetcode.com/problems/3sum/
解題想法:Two Pointers 【筆記

  • 沒加上 Line-5 時,會RE (AddressSanitizer: heap-buffer-overflow),不懂為什麼?
  • 題目要求:Find all unique triplets in the array which gives the sum of zero. 因此加上 Line-12/24/25,避免數字重複的組合。
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ans;
        if (nums.size() < 3 || (nums.size()==3 && nums[0]+nums[1]+nums[2]!=0)) return ans;

        vector<int> v;
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;
        for (int i=0; i<nums.size()-2; i++) {
            if (i==0 || (i>0 && nums[i]!=nums[i-1])){
                int l = i + 1;
                int r = nums.size() - 1;
                while (l < r){
                    if (nums[i] + nums[l] + nums[r] > 0) r--;
                    else if (nums[i] + nums[l] + nums[r] < 0) l++;
                    else{
                        v.clear();
                        v.push_back(nums[i]);
                        v.push_back(nums[l]);
                        v.push_back(nums[r]);
                        ans.push_back(v);
                        while (l<r && nums[l]==v[1]) l++;
                        while (l<r && nums[r]==v[2]) r--;
                    }
                }
            }
        }
        return ans;
    }
};
分享本文 Share with friends