The title

Leetcode-cn.com/problems/tw…

The public account “Java Programming Notes” record Java learning daily, share learning road dribs and drabs, from entry to give up, welcome to pay attention to

describe

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] Example 2:

Input: nums = [3,2,4] target = 6 output: [1,2] example 3:

Input: nums = [3,3], target = 6

Solution

The sum of two subscripts in nums is equal to the target value, find the two numbers and return the subscripts, and do not have the same element coordinates, that is, each element subscript cannot be repeated

Violent solution

Violent solution

Train of thought

The first layer for loop is from 0 to (length-1), and the second layer for loop is from the beginning of the definition of the first layer +1 to length. Fetch the value of the first layer and the value of the second layer, add equal to target, then record the subscript and return

CODE

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

The complexity of the

  • Time complexity:O(N^2), includingNIs the number of elements in the array. In the worst case, any two numbers in the array must be matched once
  • Space complexity: O(1)

The results of

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 38.7 MB, beating 35.39% of all Java commits

Hash table

Hash table

Train of thought

The disadvantage of the violent solution lies in the high time complexity of x + y == target. We need to quickly find out whether y(target-x) corresponding to X exists, that is, to quickly find the corresponding index. The hash table is a good choice, which stores the current value x and the corresponding subscript I. Check whether there is a corresponding y(target-x) in the hash table. If there is no corresponding Y (target-x) in the hash table, save x to the hash table to ensure that x does not match it

CODE

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) {
          	// Check whether the hash table has the corresponding y(target-x)
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
          	// Store the current value and the corresponding subscript
            hashtable.put(nums[i], i);
        }
        return new int[0]; }}Copy the code

The complexity of the

  • Time complexity: O(N), where N is the number of elements in the array. For each element x, we can look O(1) for target-x

  • Space complexity: O(N), where N is the number of elements in the array. Mainly the overhead of the hash table

The results of

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 38.7 MB, beating 47.28% of all Java commits