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

  • Javaimplementation
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
  • Golangimplementation
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.