1. Two Sum

Add to List

Question

Editorial Solution

My Submissions

• Total Accepted:

  382143

• Total Submissions

• Difficulty:
  Easy

Given an array of integers, returnindicesof the two numbers such that they add up to a specific target.
You may assume that each input would haveexactlyone solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13):
The return format had been changed tozero-basedindices. Please read the above updated description carefully.

思路：因为数组没有排序，所以用一个dict记录数组中的值和下标，之后遍历数组，对每个数都检查有没有另一个加起来等于target的数。因为每个数组都只有一个解，所以不用担心会有duplicate。但要注意另一个数的下标不能和当前数下标相等。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return []
        res = []
        check = {}
        for i, v in enumerate(nums):
            check[v] = i
        for j, val in enumerate(nums):
            if check.has_key(target - val) and check.get(target-val) != j:
                res.append(j)
                res.append(check[target - val])
                break
        return res

167. Two Sum II - Input array is sorted

Add to List

Question

Editorial Solution

My Submissions

• Total Accepted: 43332
• Total Submissions:
• Difficulty: Medium

Given an array of integers that is alreadysorted 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

Hide Company Tags

Amazon

思路：因为数组是排过序的，所以可以用一前一后两个指针遍历数组，如果两个数的和大于target那么大的坐标减一，反之小的坐标加一，等于时就记录下当前两个坐标。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not numbers:
            return []
        res = []
        i,j = 0, len(numbers) -1
        while i < j:
            s = numbers[i] + numbers[j] 
            if s == target:
                res.append(i + 1)
                res.append(j + 1)
                break
            elif s > target:
                j -= 1
            else:
                i += 1
        return res

170. Two Sum III - Data structure design

Add to List

Question

Editorial Solution

My Submissions

• Total Accepted: 20966
• Total Submissions
• Difficulty: Easy

Design and implement a TwoSum class. It should support the following operations:addandfind.

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

Hide Company Tags

LinkedIn

思路：这是一个设计题。因为随时可能查找，所以不能每次都sort，这样会超时，所以我们要用dict把每次加进去的数存起来。key是加进去的数，val是有多少个。当我们找value时，如果value减去当前值在dict里，并且减去的值不是自己本身，那么久返回True。

class TwoSum(object):

    def __init__(self):
        """
        initialize your data structure here
        """
        self.ctr = {}

    def add(self, number):
        if number in self.ctr:
            self.ctr[number] += 1
        else:
            self.ctr[number] = 1

    def find(self, value):
        ctr = self.ctr
        for num in ctr:
            if value - num in ctr and (value - num != num or ctr[num] > 1):
                return True
        return False

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