当前位置：首页 > article >正文

Leetcode—15.三数之和【中等】

article 2024/9/20 12:25:50

2023每日刷题（四十一）

Leetcode—15.三数之和

在这里插入图片描述

实现代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int i, j, k;
        int s, pre;
        int len = nums.size();
        for(i = 0; i < len - 2; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            pre = nums[i];
            j = i + 1;
            k = len - 1;
            while(j < k) {
                s = pre + nums[j] + nums[k];
                if(s > 0) {
                    k--;
                } else if(s < 0) {
                    j++;
                } else {
                    vector<int> tmp;
                    tmp.push_back(pre);
                    tmp.push_back(nums[j]);
                    tmp.push_back(nums[k]);
                    ans.push_back(tmp);
                    j++;
                    while(j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    k--;
                    while(j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return ans;
    }
};

运行结果

在这里插入图片描述

优化版本

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int i, j, k;
        int s, pre;
        int len = nums.size();
        for(i = 0; i < len - 2; i++) {
            pre = nums[i];
            if(i > 0 && pre == nums[i - 1]) {
                continue;
            }
            if(pre + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            if(pre + nums[len - 1] + nums[len - 2] < 0) {
                continue;
            } 
            j = i + 1;
            k = len - 1;
            while(j < k) {
                s = pre + nums[j] + nums[k];
                if(s > 0) {
                    k--;
                } else if(s < 0) {
                    j++;
                } else {
                    vector<int> tmp;
                    tmp.push_back(pre);
                    tmp.push_back(nums[j]);
                    tmp.push_back(nums[k]);
                    ans.push_back(tmp);
                    j++;
                    while(j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    k--;
                    while(j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return ans;
    }
};