今日题目有：

  • 字符串相乘
  • 三数之和

1. 字符串相乘

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例：
输入: num1 = "2", num2 = "3"
输出: "6"

思路

模拟竖式乘法的计算法则，先将字符串反转并转成数字数组，然后逐位相乘，再相加。

Swift实现

func multiply(_ num1: String, _ num2: String) -> String {
    guard num1 != "0" && num2 != "0" else {return "0"}
    let n = num1.count, m = num2.count
    var result = Array(repeating: 0, count: n + m)
    
    let num1Chars = Array(num1.reversed()).map { Int(String($0))! }
    let num2Chars = Array(num2.reversed()).map { Int(String($0))! }
    
    for i in 0..<n {
        for j in 0..<m {
            let product = num1Chars[i] * num2Chars[j]
            let sum = product + result[i + j]
            result[i + j] = sum % 10
            result[i + j + 1] += sum / 10
        }
    }
    
    while result.count > 1 && result.last == 0 {
        result.removeLast()
    }
    
    return result.reversed().map { String($0) }.joined()
}

2. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路

看到一个小tip：输出顺序和三元组顺序不重要。那么我们可以先将数组进行排序。 然后遍历，利用双指针进行搜索，对于当前遍历位置i来说，剩余两个元素的查找在[i+1, n-1]这个索引区间里面去找。根据当前得到的和的情况去前后移动指针即可。 需要注意的是，在每重循环中，都需要剔除一些重复元素来保证唯一性。

Swift实现

func threeSum(_ nums: [Int]) -> [[Int]] {
    guard nums.count >= 3 else {return []}
    let nums = nums.sorted(), n = nums.count
    var result: [[Int]] = []
    for i in 0..<nums.count {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        var left = i + 1, right = n - 1
        while left < right {
            if left > i + 1 && nums[left] == nums[left + 1] {
                left += 1
                continue
            }
            let sum = nums[i] + nums[left] + nums[right]
            if sum > 0 {
                right -= 1
            } else if sum < 0 {
                left += 1
            } else {
                result.append([nums[i], nums[left], nums[right]])
                left += 1
            }
        }
    }
    return result
}