LeetCode.两数之和和三数之和

Wu_Candy

发布于 2022-07-04 21:11:10

4060

文章被收录于专栏：无量测试之道无量测试之道

这是无量测试之道的第221篇原创

两数之和

2次for循环O( N2 ) 的做法就不说了，大家都会。我说下O(N)时间复杂度的做法。

解题思路：

一次for循环。遍历的时候用字典记录下遍历到的值，不过是以num为key，以下标index为value
继续遍历的时候，就用 target - num作为key去字典中取值，如果取到了说明存在，返回结果
若没有取到，就以num为key，index为value存入字典

代码如下：

 func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var map = [Int: Int]()
        for (i,num) in nums.enumerated() {
           if let index = map[target - num] {
               return [index, i]
           } 
           map[num] = i
        }
        return []
    }

三数之和：

其实这个题目有点难，暴力解法就是3层for循环，不过O( N3 )提交是肯定过不了的，这个题目还有一个要求就是不能重复。

解题思路： 先进行一次排序。因为这个题目考查的不是排序，所以我们可以直接使用系统自带的排序算法。

上图中，l的下标一开始是 i+1; r一开始就只想最后一个元素，下标为nums.count-1； 就以-4开始举一个例子来表述这个算法的解题思路：

开始时，i = 0, nums[i] = -4, l = i + 1, r = nums.count - 1
此时,nums[i] + nums[l] + nums[r] = -4-1+2 = -3,因为数组是排好序的，说明nums[l]太小了，所以l++;
直到l == 4,此时,nums[i] + nums[l] + nums[r] = -4+1+2 = -1还是不等于0，所以i++
此时i == 1，l = i+1 = 2，r = nums.count - 1,此时nums[i] + nums[l] + nums[r] = -1-1+2 = 0,所以将这组数据存入到结果数组中。然后l++.r--,进行下一次遍历。

代码如下：

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 { return [] }
        // 系统方法进行排序
        let sortedNums = nums.sorted()
        var result = [[Int]]()
        let lastR = sortedNums.count - 1
        for i in 0...(sortedNums.count - 3) {
        // 去重1⃣️
            if i > 0 && sortedNums[i] == sortedNums[i-1] { continue }
            var l = i + 1; var r = lastR; let remain = 0 - sortedNums[i];
            while (l < r) {
                let sumLR = sortedNums[l] + sortedNums[r]
                if sumLR == remain {
                    result.append( [sortedNums[i], sortedNums[l], sortedNums[r] ])
                    // 去重2⃣️
                    while (l < r && sortedNums[l] == sortedNums[l+1]) { l += 1 }
                    while (l < r && sortedNums[r] == sortedNums[r-1]) { r -= 1 }
                    l += 1
                    r -= 1
                } else if sumLR < remain {
                    l += 1
                } else {
                    r -= 1
                }
            }
        }
        return result
    }
}

核心是如何去重的问题。举例子来说明重复的问题，代码里面有2处重复，我标记了分别为1⃣️和2⃣️。

先看第1⃣️处去重情况：看下图红色方框选中的两个-1。因为前面一个-1已经完成一次遍历。所以再碰到同样的 -1 就直接跳过。

再看第2⃣️处去重情况：如下图所示，当i = 0, l = 2, r = 6时，nums[i] + nums[l] + nums[r] = 0,所以马上l++, r--红色的表示转换后的样子，发现l++ 和 l指的指向是一样的，所以就跳过。r 和 r--指的指向是一样的，也跳过。这样就达到去重的目的。

总结：

今天主要分享了2道常考的算法题。2数之和和3数之和。2数之和的思路就是用字典来存储，用空间换时间的方式使时间复杂度为O(N)。3数之和就比较有难度了，核心就是如何去重的问题，我也在文中举例子来表达了是如何去重的。希望能帮助到大家。

end

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自无量测试之道微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度