整理了一部分Leetcode上关于两个及两个以上数求和的问题

Two Sum

Problem: Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Example: Given nums = [2, 7, 11, 15], target = 9. Return [0, 1]
Link: https://leetcode.com/problems/two-sum/

Answer:

# Comments: time complexity of searching in dict is O(1), since dict in python is organized by hash

class Solution(object):
    def twoSum(self, nums, target):
        if len(nums) <= 1:
            return False
        buff_dict = {}
        for i in range(len(nums)):
            if nums[i] in buff_dict:
                return [buff_dict[nums[i]], i]
            else:
                buff_dict[target - nums[i]] = i

Two Sum, Input array is sorted

Problem: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Example: Given numbers = [2,7,11,15], target = 9. Return [1,2]
Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Answer 1:

class Solution:  # 两个指针往中间移动，较快
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:  # 如果等于，直接返回
                return [l + 1, r + 1]
            elif s < target:  # 如果小于，左边指针右移
                l += 1
            else:  # 如果大于，右边指针左移
                r -= 1

Answer 2:

class Solution:  # 哈希表，最快
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}
        for i, num in enumerate(numbers):  # = for i in range(len(numbers))
            if target - num in dic:
                return [dic[target - num] + 1, i + 1]
            dic[num] = i

Three Sum

Problem: 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. The solution set must not contain duplicate triplets.
Example: Given array nums = [-1, 0, 1, 2, -1, -4], return [[-1, 0, 1], [-1, -1, 2]]
Link: https://leetcode.com/problems/3sum/

Answer, copied from here:

# Comment 1: 最容易想到的是基于Two Sum的两重循环加hash，但要想到先排序是比较难的

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return list(map(list, res))

Three Sum Closest

Problem: Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers.
Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Link: https://leetcode.com/problems/3sum-closest/

Answer:

# Comment 1: can't find exact source
# Comment 2: based on Three Sum, with two pointers

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) < 3:
            return []
        
        nums.sort()
        closest = None
        closest_distance = float('inf')
        
        for i in range(len(nums[:-2])):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            l, r = i + 1, len(nums) - 1
            while l < r:
                current_sum = nums[i] + nums[l] + nums[r]
                if current_sum < target:
                    l += 1
                elif current_sum > target:
                    r -= 1
                elif current_sum == target:
                    return target
                
                current_distance = abs(current_sum - target)
                if current_distance < closest_distance:
                    closest = current_sum
                    closest_distance = current_distance
        
        return closest

Four Sum

Problem: Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. The solution set must not contain duplicate quadruplets.
Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]
Link: https://leetcode.com/problems/4sum/

Answer:

# Comment 1: can't find exact source
# Comment 2: 我写了一个基于Three Sum + 一重循环的，能提交，但毕竟还是多了一个量级
# Comment 3: 另一种思路是把Four Sum当成两个Two Sum，但并不是迭代。可以先两两计算所有可能的值，然后匹配成4元组，即如下

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not nums or len(nums) < 4: return []
        
        nums.sort()
        sum_to_ix = {}
        ans = set()
        m = len(nums)
        
        for i in range(m):
            for j in range(i+1,m):
                two_sum = nums[i] + nums[j]
                key_list = sum_to_ix.keys()
                if two_sum not in key_list:
                    sum_to_ix[two_sum] = [[i,j]]
                else:
                    sum_to_ix[two_sum].append([i,j])
                if target-two_sum in key_list:
                    for idx in sum_to_ix[target-two_sum]:
                        if i not in idx and j not in idx:
                            ans.add(tuple(sorted([nums[idx[0]],nums[idx[1]],nums[i],nums[j]])))
        return list(ans)

Combination Sum

Problem: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. The solution set must not contain duplicate combinations.
Example: Given candidates = [2,3,6,7], target = 7. A solution set is: [[7], [2,2,3]].
Link: https://leetcode.com/problems/combination-sum/

Answer, copied from here

class Solution(object):
    def combinationSum(self, candidates, target):

        solution = []

        def dfs(running, running_sum, ind):
            for i in range(ind, len(candidates)):
                next_sum = running_sum + candidates[i]
                if next_sum < target:
                    dfs(running + [candidates[i]], next_sum, i)
                elif next_sum == target:
                    solution.append(running + [candidates[i]])
                else:
                    continue

        dfs([], 0, 0)

        return solution

Appendix: 补充一段Python实现BFS和DFS的代码

graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}


def BFS(graph, s):
    """
    :param graph: graph
    :param s: startpoint
    :return: BFS path
    """
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    while len(queue) > 0:
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)


def DFS(graph, s):
    """
    :param graph: graph
    :param s: startpoint
    :return: DFS path
    """
    stack = []
    stack.append(s)
    seen = set()
    seen.add(s)
    while len(stack) > 0:
        vertex = stack.pop()
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                stack.append(w)
                seen.add(w)
        print(vertex)

Subarray Sum Equals K

Problem: Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example: Input nums = [1,1,1] and k = 2, output 2.
Link: https://leetcode.com/problems/subarray-sum-equals-k/

Answer:

# Comment: 从0到j的累积和 - 从0到i的累积和 = k，则i到j的和为k --》转化为Two Sum

class Solution:
    def subarraySum(self, nums, k):
        count = 0
        if not nums:
            return count
        mapping = {0: 1}
        cur_sum = 0
        for i in range(len(nums)):
            cur_sum += nums[i]
            if cur_sum - k in mapping:
                count += mapping[cur_sum - k]
            mapping[cur_sum] = mapping.get(cur_sum, 0) + 1
        return count

Subarray Sums Divisible by K

Problem: Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.
Example: Input A = [4,5,0,-2,-3,1], K = 5, output 7. There are 7 subarrays with a sum divisible by K = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Link: https://leetcode.com/problems/subarray-sums-divisible-by-k/

Answer:

# Comment: 从0到j的累积和 % k == 从0到i的累积和 % k --》与上题十分类似

class Solution:
    def subarraysDivByK(self, A, K):
        res = 0
        prefix = 0
        count = [1] + [0] * (K - 1)
        for a in A:
            prefix = (prefix + a) % K  # 前缀和求余
            # 若0到j前缀和与0到i上前缀和同余，则(i, j)这一子串符合要求
            res += count[prefix]
            count[prefix] += 1
        return res

Valid Triangle Number

Problem: Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example: Input nums = [2, 2, 3, 4], output 3 (223, 234, 234).
Link: https://leetcode.com/problems/valid-triangle-number/

Answer

# Comment: 3指针法。先排序，然后一个指针定位长边，两个指针（称为左右指针）在该指针的左侧搜寻可能的组合。左指针从index=0处出发，右指针从index=i-1处出发。当两短边相加大于长边时，计数right - left（中间所有元素与right的和势必都可以大于长边）同时右指针左移一位来使短边和下降；反之，左指针右移一位使短边和上升

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count = 0
        for i in range(2, len(nums)):
            left = 0
            right = i - 1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    count += right - left
                    right -= 1
                else:
                    left += 1
        return count

Subarray Product Less Than K

Problem: Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.
Example: Input: nums = [10, 5, 2, 6], k = 100; output 8.
Link: https://leetcode.com/problems/subarray-product-less-than-k/

Answer:

# Comment1: 这类找子串的问题，最方便的就是用指针设置滑动窗口。部分子序列问题，也可以先排序，然后再转化为子串问题
# Comment2: 2指针法。用O(1)空间记录当前的积，右指针从index=0处不断右移，积不断变大。当积大于目标值时，左指针从index=0处右移，积不断变小。计数就等于左右指针间距离之和。需要注意，由于nums全是正数，所以不存在任何组合积<=1

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:
            return 0
        curr_prod = 1
        l = 0
        count = 0
        for r, num in enumerate(nums):
            curr_prod *= num
            while curr_prod >= k:
                curr_prod //= nums[l]
                l += 1
            count += r - l + 1
        return count

Maximum Subarray & Maximum Sum Circular Subarray

Problem: 基本问题是寻找数组中最大的子数组和，延伸问题是针对环形数组寻找长度不超过最小周期的最大子数组和
Example: Input: [5,-3,5]; Output1: 7, Output2: 10, on [5, -3, 5, 5, -3]
Link1: https://leetcode.com/problems/maximum-subarray/description/
Link2: https://leetcode.com/problems/maximum-sum-circular-subarray/

Answer:

# Comment1: 寻找最大的子数组和使用的基本算法是[Kadane算法](https://en.wikipedia.org/wiki/Maximum_subarray_problem)
# Comment2: 算法的思想是如果元素i之前累计和为正，那么可以尝试将子数组延伸到元素i；否则元素i重新开始计算子数组和。这是一种动态规划的思想：当前状态仅依赖上一个子状态。

# Q1
class Solution:
    def maxSubArray(self, nums):
        ans = cur = float('-inf')
        for n in nums:
            cur = n + max(cur, 0)
            ans = max(ans, cur)
        return ans

# Q2: 对于环形数组，可能的情况有两种。一是在最小周期内就可以得到最大子数组和，那么直接调用Q1的方法即可；二是要从第一个周期跨越到第二个周期，但是跨越得到的子数组长度不能超过第一个周期。比如在上面的例子中，最大和是5+5，而不是5+-3+5+5。
class Solution:
    def maxSubarraySumCircular(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        def kadane(nums):
            ans = cur = float('-inf')
            for n in nums:
                cur = n + max(cur, 0)
                ans = max(ans, cur)
            return ans
        
        S = sum(A)
        ans1 = kadane(A)  # 最小周期内，与Q1完全一致
        ans2 = S + kadane(-n for n in A[1:-1])  # 跨越周期，即从尾部连接到头部，那就等于在中间找一个最小的，然后减去即可
    
        return max(ans1, ans2)