This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
1. Title Description
Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts.
You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.
You can return the answers in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code
Example 2:
Input: nums = [3,2,4], target = 6Copy the code
Example 3:
Input: nums = [3,3], target = 6Copy the code
Tip:
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
- There can only be one valid answer
Second, train of thought analysis
This is an easy algorithm problem to implement, but if you want to get the optimal algorithm, it takes some brain power. The following algorithms are available for reference:
Algorithm 1: direct loop method
It’s the easiest thing to think of, and the easiest thing to do, to double loop through each element of an array, evaluate whether the sum of the two numbers equals target, and if so, exit the loop immediately.
Algorithm 2: Hash table
It is noted that the time complexity of algorithm 1 is high because the time complexity of finding target-x is too high. Therefore, we need a better way to quickly find out if there is a target element in an array. If it exists, we need to find its index.
AC code
Algorithm 1: direct loop method
Java
implementation
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 (target == nums[i] + nums[j]) {
return new int[]{i,j}; }}}return new int[] {0}; }}Copy the code
Golang
implementation
func twoSum(nums []int, target int) []int {
for i, num1 := range nums {
for j := i + 1; j < len(nums); j++ {
if target == num1 + nums[j] {
return []int{i,j}
}
}
}
return nil
}
Copy the code
Algorithm 2: Hash table
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0]; }}Copy the code
Four,
For example, nums = [3,2,4], target = 6.
In terms of execution time, the direct loop method is the least efficient, while the hash invention appears to have improved.