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)
, includingN
Is 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