美文网首页
15. 3Sum/三数之和

15. 3Sum/三数之和

作者: 蜜糖_7474 | 来源:发表于2019-05-06 13:56 被阅读0次

    Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

    Note:

    The solution set must not contain duplicate triplets.

    Example:

    Given array nums = [-1, 0, 1, 2, -1, -4],
    A solution set is:
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

    AC代码

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ans;
            if (nums.size() < 3) return ans;
            set<vector<int>> st;
            sort(nums.begin(), nums.end());
            if (nums[0] == 0 & nums[nums.size() - 1] == 0) {
                vector<int> tmp{0, 0, 0};
                ans.push_back(tmp);
                return ans;
            }
            for (auto mid = 1; mid < nums.size() - 1; mid++) {
                int left = 0, right = nums.size() - 1;
                while (left < mid && mid < right) {
                    if (nums[left] + nums[mid] + nums[right] == 0) {
                        vector<int> tmp{nums[left], nums[mid], nums[right]};
                        st.insert(tmp);
                        left++;
                    }
                    else if (nums[left] + nums[mid] + nums[right] > 0)
                        right--;
                    else if (nums[left] + nums[mid] + nums[right] < 0)
                        left++;
                }
            }
            for (auto it = st.begin(); it != st.end(); ++it) {
                vector<int> tmp{(*it)[0], (*it)[1], (*it)[2]};
                ans.push_back(tmp);
            }
            return ans;
        }
    };
    

    优化代码

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            for (int i = 0; i < nums.size(); i++) {
                if ((i > 0) && (i < nums.size()) && (nums[i] == nums[i - 1]))
                    continue;
                int l = i + 1, r = nums.size() - 1;
                while (l < r) {
                    int s = nums[i] + nums[l] + nums[r];
                    if (s > 0)
                        r--;
                    else if (s < 0)
                        l++;
                    else {
                        res.push_back(vector<int>{nums[i], nums[l], nums[r]});
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    }
                }
            }
            return res;
        }
    };
    

    总结

    都是O(n2)的复杂度,自己写的效率还是低了,参考资料:https://www.acwing.com/solution/leetcode/content/1079/

    相关文章

      网友评论

          本文标题:15. 3Sum/三数之和

          本文链接:https://www.haomeiwen.com/subject/okproqtx.html