The topics covered in this paper are array related, including hash table, set, priority queue, sliding window, double pointer, binary search and other techniques;

Leetcode349 — Intersection of two arrays

Given two arrays, write a function to calculate their intersection. Each element in the output must be unique. We can ignore the order of the output.

We can use HashSet to find the intersection of two arrays without repeating elements.

Insert the elements of nums1 into HashSet1, which automatically duplicates the elements of array 1. Then create a new HashSet2, which iterates through group 2. If there are iterated elements in HashSet1, insert the elements into HashSet2. So the element in HashSet2 is the final result;

Public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> num1Set = new HashSet<>(); for (int i = 0; i < nums1.length; i++) { num1Set.add(nums1[i]); } HashSet<Integer> res = new HashSet<>(); for (int i = 0; i < nums2.length; i++) { if (num1Set.contains(nums2[i])){ res.add(nums2[i]); } } int[] result = new int[res.size()]; Object[] objects = res.toArray(); for (int i = 0; i < result.length; i++) { result[i] = (int) objects[i]; } return result; }Copy the code

Leetcode350 — Intersection of two arrays II

Given two arrays, write a function to calculate their intersection. The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.

The only difference between the two arrays is that the number of repeated elements can be the same as the minimum number of occurrences in both arrays.

As shown below, we can use HashMap to solve the problem; First, use HashMap to save the element in array 1 and the number of occurrences, and then traverse array 2. If there is an element traversed in HashMap, take it out and put it in the result set. Then, subtract the number of times of this element in HashMap by one. So if we go through array 2 like that, the result set is what we need;

// Leetcode350 the intersection of two arrays II Public int[] INTERSECT (int[] nums1, int[] nums2) {HashMap<Integer,Integer> nums1Map = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { nums1Map.put(nums1[i],nums1Map.getOrDefault(nums1[i],0) + 1); } ArrayList<Integer> res = new ArrayList<>(); for (int i = 0; i < nums2.length; i++) { if (nums1Map.containsKey(nums2[i])){ res.add(nums2[i]); nums1Map.put(nums2[i],nums1Map.get(nums2[i])-1); if (nums1Map.get(nums2[i]) == 0){ nums1Map.remove(nums2[i]); } } } Object[] objects = res.toArray(); int[] result = new int[objects.length]; for (int i = 0; i < objects.length; i++) { result[i] = (int) objects[i]; } return result; }Copy the code

Leetcode209 — the smallest subarray

Given an array of n positive integers and a positive integer target.

Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.

The problem is a typical sliding window can solve the type of problem, the solution is as follows;

The idea of sliding window is to maintain a [L… R] sliding window, so that the elements in the window meet the requirements, and then constantly update the final result according to the window; If the window length is smaller than the current record length, update the window length.

Public int minSubArrayLen(int target, int[] nums) {// Maintain a [l...r] sliding window int l = 0; int r = -1; int res = Integer.MAX_VALUE; int sum = 0; while (r < nums.length - 1) { if (sum < target) { r++; sum += nums[r]; } while (sum >= target) { if (r - l + 1 < res) { res = r - l + 1; } // here is the initial error, should be first nums[l], then l++ ！！！！！ // l++; // sum -= nums[l]; sum -= nums[l]; l++; } } return res == Integer.MAX_VALUE ? 0 : res; }Copy the code

Leetcode283 — Moves zero to the end of the array

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.

ArrayList = arrayList.size (); ArrayList = arrayList.size (); ArrayList = arrayList.size (); In this case, 0 is used to fill the remaining data;

Public void moveZeroes(int[] nums) {ArrayList<Integer> nonZeroElements = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] ! = 0){ nonZeroElements.add(nums[i]); } } for (int i = 0; i < nonZeroElements.size(); i++) { nums[i] = nonZeroElements.get(i); } for (int i = nonZeroElements.size(); i < nums.length; i++) { nums[i] = 0; }}Copy the code

5. Leetcode167 — sum of two numbers

Given an array of integers in ascending order numbers, find two numbers that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

The solution is shown below. This is a typical type of problem that can be solved by using left and right double Pointers.

Define two Pointers to the left and right at the beginning and end of the array. Then add the elements at the two Pointers. Because the array is ordered, if and is less than target, move the left pointer to the right one bit. If and is greater than target, move the right pointer one bit to the left; If and is equal to target, the answer is found.

Public int[] twoSum(int[] numbers, int target) {int l = 0; int r = numbers.length -1; int[] res = new int[2]; while (l < r){ if (numbers[l] + numbers[r] < target){ l++; } else if (numbers[l] + numbers[r] >target) { r--; }else { res[0] = l+1; res[1] = r+1; return res; } } return res; }Copy the code

6. Leetcode01 — sum of two numbers

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.

Solution a brute force solution iterates through a set of numbers in a two-level nested for loop until it finds two numbers that add up to target; Because it is a double-nested for loop, the time complexity is O(n^2);

Public int[] twoSum3(int[] nums, int target) {int[] res = new int[2]; // LeetCode01 twoSum3(int[] nums, int target) {int[] res = new int[2]; for (int i = 0; i < nums.length - 1; i++) { for (int j = i+1; j < nums.length; j++) { if (nums[j] + nums[i] == target){ res[0] = i; res[1] = j; } } } return res; }Copy the code

We can use HashMap to save the values and indexes of the elements in the array, and then iterate through the array to find if there is a target-traversed current value in the HashMap. If there is a target-traversed current value, the sum of two numbers is target. Return the index stored in the HashMap and the index traversed to the current value. And this process only needs to traverse the array, isn’t very clever ~ time complexity is O(n) level;

O(n) public int[] twoSum2(int[] nums, int target) {int[] res = new int[2]; HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (hashMap.containsKey(target - nums[i])){ res[0] = hashMap.get(target - nums[i]); res[1] = i; } hashMap.put(nums[i],i); } return res; }Copy the code

Leetcode804 — the only Morse code

The International Morse code defines a standard encoding for each letter to correspond to a string of dots and dashes, such as “A” for “.-“, “b” for “-…”. “, “C” for “-… – “, etc.

For convenience, all 26 English letters correspond to the Morse password table as follows:

[“, “-…” – “, “- -“, “-..”, “”,”… -… “, “-“, “… “, “.. “, “-“, “- -“, “… “, “-“, “-“, “-“, “. -. “, “-. -“, “. – “, “… “, “-” , “.. – “, “… “, “-“, “-.. -“, “- -“, “-..”]

Given a list of words, each word can be written as a combination of Morse codes for each letter. For example, “cab” can be written as “-.. -.. -…” , (i.e.” -… -.” + “.-” + “-…” String combination). We call this linking process word translation.

Returns the number of different word translations we can get for all words.

Translate all the words in the array into Morse passwords and save them in the HashSet. Return the size of the HashSet, since the HashSet is automatically de-duplicates.

/ / 804 yards only Moore Smith leetcode public int uniqueMorseRepresentations (String [] words) {HashSet < String > set = new HashSet < > (); for (String word : words) { String morseCode = transformWordToMorseCode(word); set.add(morseCode); } return set.size(); } private String transformWordToMorseCode(String word) { String[] morse = {".-","-..." , "- -", "-.." , "",".. -. ", "-- --.", "..." , ".." , "-", "- -", "..." , "-", "-", "-", ". -. ", "-- --", ". - ", "..." , "-", ".. - ", "... - ", "-", "-.. - ", "- -", ".." }; char[] chars = word.toCharArray(); StringBuilder builder = new StringBuilder(); for (int i = 0; i < chars.length; i++) { builder.append(morse[chars[i] - 'a']); } return builder.toString(); }Copy the code

8. Leetcode75 — Color classification

Given an array of n red, white, and blue elements, sort them in place so that the elements of the same color are adjacent and sorted in red, white, and blue order.

In this case, we used integers 0, 1, and 2 to represent red, white, and blue, respectively.

The solution is shown below. We can solve this problem by using the idea of three-way quicksort. Left when the element is 0, middle when the element is 1, right when the element is 2, and then we’re done sorting, O(n) time;

Public void sortColors(int[] nums) {int l = 0; int r = nums.length - 1; int m = l -1; int n = r + 1; // after the loop is completed [l...m] indicates 0; (m... N) represents 1; [n...r] stands for 2; for (int i = 0; i < n; ) { if (nums[i] == 0){ swap(nums,m+1,i); m++; i++; }else if (nums[i] == 2){ swap(nums,n-1,i); n--; }else { i++; Private void swap(int[] nums, int a, int b) {int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; }Copy the code

9. Leetcode347 — the first K high-frequency elements

Given an integer array nums and an integer k, return the element with the highest frequency k. You can return the answers in any order.

The solution is shown below. This problem combines hash tables and priority queues nicely. We start by iterating through one array, storing the elements and their occurrences in a HashMap. Then create a new priority queue, using the HashMap value subtraction as the comparator, so that the higher the frequency of the number, the lower its priority. The last HashMap is traversed, and if the element in the priority queue is less than K, it is put directly. Otherwise, the first element in the queue is compared with the traversed element. If the traversed element is more frequently than the first element in the queue, the first element is removed from the queue and the traversed element is put in the queue. Because the element at the head of the queue is always the least frequent in the priority queue;

Because it’s only traversing the array twice, it’s O(2n), ignoring the constants, it’s O(n);

Public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int num : nums) { hashMap.put(num, hashMap.getOrDefault(num, 0) + 1); } PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer a,  Integer b) { return hashMap.get(a) - hashMap.get(b); }}); for (Integer key : hashMap.keySet()) { if (queue.size() < k){ queue.add(key); }else if (hashMap.get(key) > hashMap.get(queue.peek())) { queue.remove(); queue.add(key); } } int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = queue.remove(); } return res; }Copy the code

Leetcode454 — a tuple whose sum of four numbers is 0

Given four arraylists A, B, C, D that contain integers, calculate how many tuples (I, j, k, L) there are such that A[I] + B[j] + C[k] + D[L] = 0.

To keep things simple, all A, B, C, and D have the same length N, and 0 ≤ N ≤ 500. All integers range from -2^28 to 2^ 28-1, and the final result does not exceed 2^ 31-1.

Solution — Violent solution

Directly use four layers of nested for loop to iterate over the number group, but this method of time complexity is O(n^4) level, poor performance;

// Leetcode454 tuple with the sum of four numbers 0 // Violent solution quadruple loop, time complexity O(n^4), explosion, Public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0; for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { for (int k = 0; k < nums3.length; k++) { for (int l = 0; l < nums4.length; l++) { if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) { res ++; } } } } } return res; }Copy the code

Solution two uses a hash table

A two-level nested for loop is used to iterate over the first two arrays, storing all the sums of the first two arrays and their occurrences in a HashMap. Then a double-layer nested for loop iterates through the last two arrays, looking for the negates of the sum of the two array elements in the HashMap, adding the value of the HashMap.

// With hashmap, Public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {//key represents the sum of the elements nums1 and nums2, Value Number of and HashMap<Integer,Integer> HashMap = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { for (int j = 0; j < nums2.length; j++) { int sum = nums1[i] + nums2[j]; hashMap.put(sum,hashMap.getOrDefault(sum,0) + 1); } } int res = 0; for (int i = 0; i < nums3.length; i++) { for (int j = 0; j < nums4.length; j++) { int sum = nums3[i] + nums4[j]; if (hashMap.containsKey(-sum)){ res+=hashMap.get(-sum); } } } return res; }Copy the code

Leetcode704 — binary search for ordered arrays

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

Binary search of ordered array is a classic algorithm problem, because the array is ordered, every time to the middle of the array search, if the middle number is smaller than target, to the right of the subarray search; If the middle number is larger than target, look in the left subarray. If equal to target, return directly; This reduces the element by half after each search, and the time complexity is O(logn) level;

Public int search(int[] nums, int target) {int l = 0; int r = nums.length - 1; while (l <= r){ int mid = l + (r - l) / 2; if (nums[mid] < target){ l = mid + 1; }else if (nums[mid] > target){ r = mid - 1; }else { return mid; } } return -1; }Copy the code

12. Leetcode217 — There are duplicate elements

Given an array of integers, determine whether there are duplicate elements.

The function returns true if there is a value that appears in the array at least twice. Return false if each element in the array is different.

A HashSet cannot store duplicate elements. The time complexity is O(n).

Public Boolean containsDuplicate(int[] nums) {HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (set.contains(nums[i])){ return true; } set.add(nums[i]); } return false; }Copy the code

13. Leetcode219 — There are duplicate elements II

Given an array of integers and an integer k, determine whether there are two different indexes I and j in the array such that nums [I] = nums [j] and the absolute value of the difference between I and j is at most K.

Save the values and indexes of the elements in the array into the HashMap and iterate over the number group. If there are elements traversed in the HashMap and the index difference is less than or equal to k, return true. If there is no such thing, return false;

In this case, the process is also clever because it only needs to go through the array once, and the time complexity is O(n) level;

Public Boolean containsNearbyDuplicate(int[] nums, int k) {HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (hashMap.containsKey(nums[i]) && Math.abs(i - hashMap.get(nums[i])) <= k) { return true; } hashMap.put(nums[i], i); } return false; }Copy the code

14. Leetcode220 — There are duplicate elements III

You are given an array of integers nums and two integers k and t. Abs (nums[I] -nums [j]) <= t, and abs(i-j) <= k.

Returns true if it exists, false if it does not.

First we need to know what the two apis mean; TreeSet treeSet = new TreeSet<>(); treeSet.ceiling(6); Ceiling represents the smallest value greater than 6 in a treeSet; treeSet.floor(6); Floor represents the largest value in a treeSet less than 6;

The solution is as follows. In this case, the order of TreeSet elements is used, because its underlying implementation is red-black tree, so the order of elements can be guaranteed.

Treeset. ceiling((long) nums[I] – (long) t) <= (long) nums[I] + (long) t = abs(nums[I] -nums [j]) <= t; Treeset.size () == k + 1; treeset.size () == k + 1; treeset.size () == k + 1; So we met both conditions with TreeSet;

In this case, the array is traversed only once and the time complexity is O(n).

/ / 220 duplicate elements leetcode III public Boolean containsNearbyAlmostDuplicate (int [] nums, int k, int t) { TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { if (treeSet.ceiling((long) nums[i] - (long) t) ! = null && treeSet.ceiling((long) nums[i] - (long) t) <= (long) nums[i] + (long) t) { return true; } treeSet.add((long) nums[i]); if (treeSet.size() == k + 1) { treeSet.remove((long) nums[i - k]); } } return false; }Copy the code

Source of the question

Source: LeetCode link: leetcode-cn.com/problemset/…