数据结构和算法 -- TWO-SUM 问题和python dict

打尽 two-sum 问题。

策略 & 注意点

Assumption

• array is sorted?
• each input would have exactly one solution?
• duplicates in array?
• return index is sorted?

策略

1. 头尾指针，经典模板

   while start<end:
       sum=numbers[start]+numbers[end]
       if sum==target:
           return [start,end]
       if sum>target:
           end-=1
       else:
           start+=1

2. 加上去重的模板：

   while start<end:
       cur_sum=nums[start]+nums[end]
       if cur_sum<target:
           start+=1
       elif cur_sum>target:
           end-=1
       else:
           cur_res.append([nums[0],nums[start],nums[end]])
           start+=1
           end-=1
           while start<end and nums[start]==nums[start-1]:
               start+=1
           while start<end and nums[end]==nums[end+1]:
               end-=1

3. Hashmap 来 search target-nums[i]，1－pass 先 check 在不在 map 中，不在就放进去。

注意点

• 涉及 index 一般就不先 sort 了，因为会 disrupt the order
• 如果上来就把整个 list 转成 hashmap，之后在 search，那么就要注意 val==target-val 的情况了，也要判断 val 出现几次（hashmap 必须考虑 key 是否会重复）
• 要去重的问题用两个 pointer 可以顺便去重，但要注意保证大条件 start<end
• 注意数字可能是 negative，初始化变量不要想当然的为0，计算 difference 的时候用 abs(n) 绝对值。
• python dict 的用法，哪些 O(1) 哪些 O(n)

例题

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

'''
Check assumption:
- array is not sorted
- each input would have exactly one solution
- duplicates in array
- return index is not sorted

Corner case:
- len(nums)<2 or nums==None

Solution:
- Loop array, search target-nums[i] for each nums[j] on the right. Time complexity: O(n^2)

Attention:
- we cannot sort array, compare target and sum and move pointers to get the answer as it would disrupt the order
- array.index(value) returns first match, but this may not be what you expect

Optimization:
- While loop, use hashmap<target-nums[i],i> to store remaining index and value, so that the second loop will have O(1) time complexity, and the total complexity would be O(n). The cost is space complexity. This is two-pass solution.
- Two-pass --> One pass. While loop, for each i, check if it is in hashmap, if not, add it to the hashmap, if exists, return index.
'''

class Solution(object):

    # with hashmap
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums)<2:
            return None
        hashmap=dict()
        for index,value in enumerate(nums):
            if target-value in hashmap:
                return[index,hashmap[target-value]]
            hashmap[value]=index
        return None


    '''
    # two loops
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums)<2:
            return None
        for index1,value in enumerate(nums):
            for index2 in range(index1+1,len(nums)):
                if nums[index2]==target-value:
                    return [index1,index2]
        return None
    '''

167. Two Sum II - Input array is sorted

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. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not numbers or len(numbers)<2:
            return None
        start=0
        end=len(numbers)-1
        while start<end:
            sum=numbers[start]+numbers[end]
            if sum==target:
                return [start+1,end+1]
            if sum>target:
                end-=1
            else:
                start+=1
        return None

170. Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

'''
Data structure:
- hashmap<number,frequency>.   Use hashmap because duplicates matter!

Corner case:
- hashmap is None

Attention:
- avoid case val==target-val

Time complexity:
- add() O(1)
- find() O(n)

About python dictionary:
- Do not use dict.keys!
In Python 2 dict.keys() creates the whole list of keys first that's why it is an O(N) operation, while key in dict is an O(1) operation.
>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 170 ns per loop
>>> %timeit 10000 in dic.keys()
100 loops, best of 3: 4.98 ms per loop
>>> %timeit 10000 in dic.iterkeys()
1000 loops, best of 3: 402 us per loop
>>> %timeit 10000 in dic.viewkeys()
1000000 loops, best of 3: 457 ns per loop

- Use dict.get(key,default=None)!
self.hashmap[number]=self.hashmap.get(number,0)+1
'''
class TwoSum(object):

    def __init__(self):
        """
        initialize your data structure here
        """
        self.hashmap=dict()

    def add(self, number):
        """
        Add the number to an internal data structure.
        :rtype: nothing
        """
        '''
        if self.hashmap.has_key(number):
            self.hashmap[number]+=1
        else:
            self.hashmap[number]=1
        '''
        self.hashmap[number]=self.hashmap.get(number,0)+1

    def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        if not self.hashmap:
            return False
        for v in self.hashmap:
            if value-v in self.hashmap:
                if self.hashmap[v]>1 or v!=value-v:
                    return True
        return False


# Your TwoSum object will be instantiated and called as such:
# twoSum = TwoSum()
# twoSum.add(number)
# twoSum.find(value)

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S 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.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

'''
Solution:
- convert to 2-sum problem, avoid duplicate triplets: sort the array, move pointers to skip duplicates

Attention:
- when avoiding duplicates, keep in mind start<end, consider corner case [0,0,0] with 0

'''
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        nums=sorted(nums)
        result=[]
        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            result+=self.twoSum(nums[i:],0-nums[i])
        return result


    def twoSum(self,nums,target):
        if len(nums)<3:
            return []
        start,end=1,len(nums)-1
        cur_res=[]
        while start<end:
            cur_sum=nums[start]+nums[end]
            if cur_sum<target:
                start+=1
            elif cur_sum>target:
                end-=1
            else:
                cur_res.append([nums[0],nums[start],nums[end]])
                start+=1
                end-=1
                while start<end and nums[start]==nums[start-1]:
                    start+=1
                while start<end and nums[end]==nums[end+1]:
                    end-=1
        return cur_res

259. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up:
Could you solve it in O(n2) runtime?

'''
Same with normal 3sum problem, just consider all possibilities.

Solution:
- sort nums, for nums[i] in nums, search if nums[start]+nums[end]<target-nums[i] for nums[i+1:], if it is, count+=end-start and keep going
'''
class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums)<3:
            return 0
        count=0
        nums=sorted(nums)
        for i in range(len(nums)):
            start=i+1
            end=len(nums)-1
            while start<end:
                cur_sum=nums[start]+nums[end]
                new_target=target-nums[i]
                if cur_sum<new_target:
                    count+=end-start
                    start+=1
                else:
                    end-=1
        return count

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

'''
Simliar to 3sum problem, but have a global_diff to record current minimum difference (remember it should be absolute value) and global_sum to record current closet result
'''
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums)<3:
            return None
        nums=sorted(nums)
        global_diff=abs(target-nums[0])
        global_sum=sum(nums[0:3])
        for i in range(len(nums)-2):
            start=i+1
            end=len(nums)-1
            cur_target=target-nums[i]
            while start<end:
                sum2=nums[start]+nums[end]
                if sum2<cur_target:
                    if abs(cur_target-sum2)<global_diff:
                        global_sum=sum2+nums[i]
                        global_diff=abs(cur_target-sum2)
                    start+=1
                elif sum2>cur_target:
                    if abs(sum2-cur_target)<global_diff:
                        global_diff=abs(sum2-cur_target)
                        global_sum=sum2+nums[i]
                    end-=1
                else:
                    return target
        return global_sum

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [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]
]

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums)<4:
            return []
        res=[]
        nums=sorted(nums)
        for i in range(len(nums)-3):
            if i>0 and nums[i]==nums[i-1]:
                continue
            res+=self.sum_3(nums[i:],target-nums[i])
        return res

    def sum_3(self,nums,target):
        if len(nums)<4:
            return []
        res=[]
        cur=nums[0]
        nums=nums[1:]
        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            new_target=target-nums[i]
            start=i+1
            end=len(nums)-1
            while start<end:
                cur_sum=nums[start]+nums[end]
                if cur_sum>new_target:
                    end-=1
                elif cur_sum<new_target:
                    start+=1
                else:
                    res.append([cur,nums[i],nums[start],nums[end]])
                    start+=1
                    end-=1
                    while start<end and nums[start]==nums[start-1]:
                        start+=1
                    while start<end and nums[end]==nums[end+1]:
                        end-=1
        return res

dict 详解

内置函数和方法

序号	函数及描述
1	cmp(dict1, dict2) 比较两个字典元素。
2	len(dict) 计算字典元素个数，即键的总数。
3	str(dict) 输出字典可打印的字符串表示。
4	type(variable) 返回输入的变量类型，如果变量是字典就返回字典类型。

Python字典包含了以下内置方法：

序号	函数及描述
1	radiansdict.clear() 删除字典内所有元素
2	radiansdict.copy() 返回一个字典的浅复制
3	radiansdict.fromkeys() 创建一个新字典，以序列seq中元素做字典的键，val为字典所有键对应的初始值
4	radiansdict.get(key, default=None) 返回指定键的值，如果值不在字典中返回default值
5	radiansdict.has_key(key) 如果键在字典dict里返回true，否则返回false
6	radiansdict.items() 以列表返回可遍历的(键, 值) 元组数组
7	radiansdict.keys() 以列表返回一个字典所有的键
8	radiansdict.setdefault(key, default=None) 和get()类似, 但如果键不存在于字典中，将会添加键并将值设为default
9	radiansdict.update(dict2) 把字典dict2的键/值对更新到dict里
10	radiansdict.values() 以列表返回字典中的所有值

时间复杂度

下表 python 3 中 dictinoary (包括 dict 和 defaultdict) 的时间复杂度，要注意的 d.keys() 在 python 2 中的复杂度是 O(n)，因为它返回的是一个 list

Operation	Example	Class	Notes
Index	d[k]	O(1)	——————————
Store	d[k] = v	O(1)	——————————
Length	len(d)	O(1)	——————————
Delete	del d[k]	O(1)	——————————
get/setdefault	d.method	O(1)	——————————
Pop	d.pop(k)	O(1)	——————————
Pop item	d.popitem()	O(1)	——————————
Clear	d.clear()	O(1)	similar to s = {} or = dict()
Views	d.keys()	O(1)	——————————
Construction	dict(…)	O(len(…))	depends # (key,value) 2-tuples
Iteration	for k in d:	O(N)	all forms: keys, values, items

So, most dict operations are O(1).

defaultdicts support all operations that dicts support, with the same complexity classes (because it inherits all the operations); this assumes that calling the constructor when a values isn’t found in the defaultdict is O(1) - which is true for int(), list(), set(), … (the things commonly used)

参考链接
Python TimeComplexity
Complexity of Python Operations