leetcode-15-3Sum-三数之和

3Sum

解题思路

此题主要是使用了二分查找的变形

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i < len; i++) {
            int a, b, c;
            a = nums[i];
            if(i > 0 && nums[i - 1] == a) continue;
            if(a > 0) break;
            int st = i + 1;
            int en = len - 1;
            while(st < en) {
                b = nums[st];
                c = nums[en];
                int t = a + b + c;
                if(t == 0) {
                    result.push_back({a, b, c});
                    while(st < en && nums[st] == b) st++;
                    while(st < en && nums[en] == c) en--;
                } else if(t > 0) {
                    en--;
                } else {
                    st++;
                }
            }
        }
        return result;
    }
};