1.Two-Sum

1. Two Sum

题目地址

https://www.lintcode.com/problem/two-sum/description

https://leetcode.com/problems/two-sum/

题目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

代码

Approach #1 Brute Force

class Solution {
  public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] == target - nums[i]) {
          return new int[] {i, j};
        }
      }
    }

    return null;
  }
}

Approach 1: One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0) return null;

    Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
    int index1 = 0, index2 = 0;
    for (int i = 0; i < nums.length; i++) {
      if (hashmap.containsKey(target - nums[i])) {
        index1 = hashmap.get(target - numsp[i]);
        index2 = i;
        return new int[]{index1, index2};
      } else {
        hashmap.put(nums[i], i);
      }
    }

    return null;
  }
}

Approach 2: Sort

对数组进行排序，然后使用binary search搜索target

class Solution {
  public:
        vector<int> twoSum(vector<int> &num, int target) {
        vector<int> result;
        const int length = nums.size();
        if (0 == length) return result;
        // map num value and index
        vector<pair<int, int>> num_index(length);
        for (int i = 0; i != length; ++i) {
          num_index[i].first = nums[i];
          num_index[i].second = i + 1;
        }

        sort(num_index.begin(), num_index.end());
        int start = 0, end = length - 1;
        while (start < end) {
          int s = num_index[start].first + num_index[end].first;
          if (s > target) {
            --end;
          } else if (s == target) {
            int min_index = min(num_index[start].second, num_index[end].second);
            int max_index = max(num_index[start].second, num_index[end].second);
            result.push_back(min_index);
            result.push_back(max_index);
            return result;
          } else {
            ++start;
          }
        }
        return result;
      }
}

Approach 3: Two-pass Hash Table

Complexity Analysis:

• Time complexity : O(n). We traverse the list containing nn elements exactly twice. Since the hash table reduces the look up time to O(1), the time complexity is O(n).

• Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (map.containsKey(complement) && map.get(complement) != i) {
        return new int[] {i, map.get(complement)};
      }
    }
  }
}