This article is participating in the “Java Theme Month – Java Brush questions card”, activity link

Topic describes

Input parameters:

  • An integer array in numbers with a tentative length range [2,103] and an internal value range [-109,109].

  • An integer field target, value range [-109,109]

Title logic:

  • Find the two integers in the array where and are the target values

Output result:

  • Returns the two integers whose sum is the target value and their array subscripts

Special note:

  • Disallow: reuse of the same elements in this array

  • Assumption: There is only one answer for each type of input

The subject sample

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

Thought analysis

Brute force method

  • Brute force cracking:

    • Iterate over each element A and find if there is a target element whose value b is equal to target-a.

      or

    • Iterate over each element A and find if there is a value b that satisfies the condition a+b=target.

Hash table solution

It turns out we can do it all at once. As we iterate and insert elements into the table, we also check back to see if the target element for the current element already exists in the table. If it exists, we have found the counterpart and returned it immediately.

AC code:

Brute force method

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, n = nums.length; i < n; ++i) {
            int num = target - nums[i];
            if (map.containsKey(num)) {
                // The result is returned directly
                return new int[]{map.get(num), i};
            }
            map.put(nums[i], i);
        }
        return null; }}Copy the code

Hash table solution

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

Conclusion:

In general, there may be a better solution than the brute force solution and hash table solution, depending on more powerful data structure, hope to have better solution partners can provide more ideas.