力扣1-两数之和&力扣15-三数之和

简介: 力扣1-两数之和&力扣15-三数之和

两数之和

原题链接:https://leetcode.cn/problems/two-sum/

题目描述

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6

输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6

输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

方法一:暴力破解

第一种方法:循环遍历

题目要求在数组中找两个数,这两个数不相等,并且和为目标值。

那么思路就是设置两个循环,从原数组中遍历,判断和是否等于目标值,并判断两数是否相异。

应注意的是,返回的是该元素在数组中的下标,而非元素本身。

这个方法思路很简单,直接上代码

为什么标题叫暴力破解呢?因为从头到尾都循环一遍了,暴力破解就是把每个可能的值都举出来判断一下,比较费时。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int index1 = 0; index1 < nums.size(); index1++)
        {
            for (int index2 = index1 + 1; index2 < nums.size(); index2++)
            {
                if (nums[index1] + nums[index2] == target)
                {
                    return { index1,index2 };
                }
            }
        }
        return {};
    }
};

运行结果

57 / 57 个通过测试用例

执行用时: 296 ms

内存消耗: 9.9 MB

可见,暴力破解的方法,比较费时

方法二:哈希表

哈希表就是一个map容器,一次能存储一个对组,对组的第一个元素为key值,用于索引,第二个元素为value值,是实值。通过.find();的方法,能够查找map容器中的key值,返回一个迭代器,利用间接访问操作符何以获取到实值。

观察暴力破解的代码,可以发现,每次执行外层的for循环,内层的for循环都会从头到尾执行一遍,执行是为了获取符合条件的数据,但该数据被多次取出。

因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用哈希表,可以将寻找index2的时间复杂度降低到从O(N)降低到O(1)。

如果事先将数据存到map中,检索到符合条件的元素提前退出,免去执行多轮不必要的查找。

也许可以优化时间。

上代码

也可以使用orderedset

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int>mp;
        for (int i = 0; i < nums.size(); i++)
        {
            if (mp.find(target - nums[i]) != mp.end())
            {
                return { i,mp.find(target - nums[i])->second };
            }
            mp.insert(make_pair(nums[i], i));
        }
        return {};
    }
};

运行结果

57 / 57 个通过测试用例

执行用时: 8 ms

内存消耗: 11 MB

如图,使用哈希表后,时间大幅降低。

三数之和

原题链接:https://leetcode.cn/problems/3sum/

题目描述

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。

请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]

输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]

输出:[]

解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]

输出:[[0,0,0]]

解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

三个指针

先按从小到大排序(从大到小也可以,下面以从小到大排序为例)。

创建三个变量,用于标记三个位置:

  1. NOW,随循环移动,表示当前循环的位置。
  2. LEFT,每轮循环重定向到NOW右侧,根据和的情况向右修正位置。
  3. RIGHT,每轮循环开始时重定向到数组最右端,根据和的情况想左修正位置。

判断三个指针指向的值的和与零的关系:

  • 如果和小于零,说明值偏小,LEFT右移
  • 如果和等于零,说明值偏大,RIGHT左移
  • 如果和等于零,添加到结果数组中,结果数组是一个存储整型数组的数组

代码第一版

听着不难,来写一下吧

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int left(0), right(0), now(0);
        vector<vector<int>>result;
        sort(nums.begin(), nums.end());
        for (; now < nums.size() - 1; now++)
        {
            left = now++;
            right = nums.size() - 1;
            while (nums[left] + nums[right] + nums[now] != 0 && left < right)
            {
                if (nums[left] + nums[right] + nums[now] < 0)
                    left++;
                else
                    right--;
            }
            if (nums[left] + nums[right] + nums[now] == 0)
                result.push_back({ nums[now],nums[left],nums[right] });
        }
        return result;
    }
};

运行结果

看示例,感觉应该能通过

提交之后,出现了问题:在处理[0,0,0,0]时,返回了两遍相同的结果。

原因是上面的代码中,碰到符合条件的就直接添加到结果数组中了。

由于每次会返回三个值,所以当出现四个或以上重复值的时候,这个问题就会出现。

这也是本题比较麻烦的一点:如何去重。

修改后

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

附上力扣大佬的注释

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重方法,将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    // 找到答案时,双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

运行结果

执行用时:120 ms, 在所有 C++ 提交中击败了42.00%的用户

内存消耗:23.3 MB, 在所有 C++ 提交中击败了45.57%的用户

通过测试用例:312 / 312

哈希表

思路跟三个指针、处理两数之和的方法类似,不同的是遍历的方法:由指针换成了表。

但在本题中,并没有表现出更好的性能。

由于这次我们要返回的是值而非下标,因此不需要使用map容器。

以下注释来自力扣大佬的分享。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零,那么不可能凑成三元组
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 2
                    && nums[j] == nums[j - 1]
                    && nums[j - 1] == nums[j - 2]) { // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
                    result.push_back({ nums[i], nums[j], c });
                    set.erase(c);// 三元组元素c去重
                }
                else {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

运行结果

超时

共勉

目录
相关文章
|
1月前
|
C++
Leetcode第一题(两数之和)
这篇文章介绍了解决LeetCode第一题“两数之和”的两种方法:暴力法和哈希表法,并提供了相应的C++代码实现。
28 0
Leetcode第一题(两数之和)
|
1月前
|
存储 C++ 容器
【LeetCode 13】1.两数之和
【LeetCode 13】1.两数之和
15 0
|
3月前
|
存储 索引
LeetCode------两数之和(3)【数组】
这篇文章介绍了LeetCode上的"两数之和"问题,提供了两种解法:一种是暴力求解法,通过双层循环遍历数组元素对查找两数之和为目标值的索引,时间复杂度为O(n^2);另一种是使用HashMap优化,通过存储元素值和索引,时间复杂度降低到O(n)。
LeetCode------两数之和(3)【数组】
|
3月前
|
算法
LeetCode第1题两数之和
该文章介绍了 LeetCode 第 1 题两数之和的解法,通过使用 HashMap 来记录数组元素及其下标,以 O(n)的时间复杂度解决问题。
|
3月前
|
JavaScript 前端开发 PHP
leetcode——两数之和【一】
leetcode——两数之和【一】
28 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
39 0
|
5月前
|
存储 算法 索引
力扣经典150题第四十三题:两数之和
力扣经典150题第四十三题:两数之和
30 1
|
5月前
|
算法 测试技术 程序员
力扣经典150题第二十七题:两数之和 II - 输入有序数组
力扣经典150题第二十七题:两数之和 II - 输入有序数组
30 1
|
5月前
力扣-两数之和
力扣-两数之和
|
5月前
|
算法 数据挖掘 Java
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)