Leetcode:三数之和

掌握程度：★ ★ ☆

只想到了暴力发，三成for循环暴力。

看题解，排序 + 双指针。

看见排序就复习了一下快速排序，真的是很容易忘记。

快速排序

挖坑填数 + 分治的思想。

void quickSort(vector<int> &nums, int left, int right) {
    if (left < right) {
        int id = partition(nums, left, right);
		//分别递归基准的左边和右边。
        quickSort(nums, 0, id - 1);
        quickSort(nums, id + 1, right);
    }
}

int partition(vector<int> &nums, int left, int right) {
    //选取一个基准数
    int base = nums[left];
	//将大于基准数的放在右边，小于基准数的放在左边，并返回基准位置。
    while (left < right) {
        while (left < right && nums[right] >= base) {
            right--;
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= base) {
            left++;
        }
        nums[right] = nums[left];
    }
    nums[left] = base;
    return left;
}

排序+双指针

排序确保，相同的元素排在一起，就可以通过相邻两个元素是否相等来去重。

vector<vector<int>> threeSum(vector<int>& nums) {
	//排序用上面的快速排序，时间超限了，std的排序比较快。
    std::sort(nums.begin(),nums.end());

    int len = nums.size();
    std::vector<std::vector<int>> ans;
    for (int i = 0; i < len; ++i) {
        if (i > 0 && nums[i] == nums[i-1]){continue;}
        int left = i + 1;
        int right = len - 1;
        while (left<right){
            int res = nums[i]+nums[left]+nums[right];
            if (res == 0){
                ans.push_back({nums[i],nums[left],nums[right]});
                left++;
                right--;
                //去重，若左边当前的数，和上一个数相同，那么这个数不用再计算了。
                while (left < right && nums[left] == nums[left-1]){
                    left++;
                }
                //去重，同理
                while (left<right && nums[right] == nums[right+1]){
                    right--;
                }
                continue;
            }else if (res>0){
                right--;
            }else if (res <0){
                left++;
            }
        }
    }
    return ans;
}