describe
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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].Copy the code
Train of thought
A for loop is used to determine the current number, and a nested for loop matches the second number, returning once the requirement is met.
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] out = new int[2];
for(int i =0; i<nums.length; i++){boolean flag = false;
for(int j =i+1; j<nums.length; j++){if(nums[i] + nums[j] == target){
out[0] = i;
out[1] = j;
flag = true;
break; }}if(flag){
break; }}returnout; }}Copy the code
Can be violent AC, but time and space complexity is not very good.
To optimize the
You can see that map is used as an auxiliary query tool in the discussion area, which can greatly improve the speed of data retrieval.
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i);
}
return result;
}Copy the code
The idea of the algorithm is as follows: the for loop is used to traverse, and the current data is the position recorded by I, but the difference is that it searches forward and matches the current data with the data that has been traversed before. In this way, the traversed data can be added to the map set, which facilitates comparison, saves retrieval time and rollback time, and avoids the problem of second match success.
You can see a huge increase in time complexity and an increase in space expenditure.