LeetCode 01 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].
  题目翻译：给定一个int数组，返回两个数的下标，这两个数的和等于给定的第二个参数target; 假定每一组输入有一组正确解。

题目分析一

最普通的思路是两个for循环查找，该算法的复杂度是 n^2; 优化的思路是：快排再夹逼查找，复杂度是 n*log(n)

package com.linsiyue;

import java.lang.*;
import java.util.Arrays;

public class leet1 {
    static class Pair implements Comparable<Pair> {
        int value, index;
        public Pair(int v, int id) {
            value = v;
            index = id;
        }        
        @Override
        public int compareTo(Pair b) {
            return this.value-b.value;
        }
    }
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Pair[] pairs = new Pair[nums.length];
        for (int i = 0; i < pairs.length; i++) {
            pairs[i] = new Pair(nums[i], i);
        }
        Arrays.sort(pairs);
        
        int left = 0, right = nums.length-1, sum = 0;
        while (left < right) {
            sum = pairs[left].value + pairs[right].value;
            if (sum == target) {
                res[0] = pairs[left].index;
                res[1] = pairs[right].index;
                if (res[0] > res[1]) {
                    int tmp = res[0];
                    res[0] = res[1];
                    res[1] = res[0];
                }
                break;
            } else if (sum > target) {
                right -= 1;
            } else {
                left += 1;
            }
        }
        return res;
    }
}

# coding: UTF-8
'''
Created on Apr 2, 2016

@author: lin
'''
# sort 是 list内置的排序方法，list 本身被修改；sorted 是 python 内置的全局排序函数， 保留原来的list
# 复杂度从 O(n**2) 降到 O(n*log(n))

class Solution(object):
    def twoSum(self, nums, target):
        sorted_num = sorted(nums)
        left = 0
        right = len(nums)-1
        
        while(left<right):
            sum = sorted_num[left]+sorted_num[right]
            if  sum == target:
                break
            elif sum > target:
                right -= 1
            else:
                left += 1
            
        pos1 = nums.index(sorted_num[left])
        pos2 = nums.index(sorted_num[right])
        if pos1 == pos2:
            pos2 = nums[pos1+1:].index(sorted_num[right]) + pos1 + 1
        
        return min(pos1, pos2), max(pos1, pos2)
            
solution = Solution()
print(solution.twoSum([0,1,1,0], 0))  

题目分析二

O(n)算法，HashMap实现，Python用字典

package com.linsiyue;

import java.lang.*;
import java.util.Arrays;

public class leet1 {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; map.put(nums[i], i++)) {
            if (map.containsKey(target - nums[i]))
                return new int[]{map.get(target - nums[i]),i};
        }
        return new int[]{-1, -1};
    }
}

# coding: UTF-8 
''' 
Created on Apr 2, 2016 
 
@author: lin 
''' 
class Solution(object): 
    def twoSum(self, nums, target):
        d = {}
        for index, num in enumerate(nums):
            if target-num in d:
                return d[target-num], index
            d[num] = index

# 测试一下    
solution = Solution() 
print(solution.twoSum([0,1,1,0], 0))