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)};
}
}
}
}