Leetcode array

This is my third article on getting started

1. 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 value target and return their array subscripts.

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Their thinking

1. The method of violence

Compare pairwise numbers and sums

Complexity:
  • Time complexity: O(n^2), where n is the array length
  • Space complexity: O(1)

2. A hash table

For each x in the array, the time to find target-x is O(n^2). If we use hash tables to store each number in the array, the time to find target-x can be reduced to O(1).

Complexity:
  • Time complexity: O(n), where n is the array length
  • Space complexity: O(n), where n is the array length

AC code

  1. Violence law

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

  2. Hash table

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

88. Merge two ordered arrays

Merge nums2 into nums1 *, * to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

Example 1:

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]Copy the code

Their thinking

1. Merge and sort

Add elements from nums2 to nums1 and sort nums1

Complexity:

  • Time complexity: O((m+n) log(m+ N)), the time complexity of fast sorting
  • Space complexity: O(log(m+ N)), the space complexity of fast sorting

2. Two-pointer method

Method 1 does not use the ordered nature of nums1 and nums2 in the title. It can use two Pointers I and j to point to the subscripts of nums1 and nums2 respectively and compare them according to the subscripts, but a new array is required to store the results

Complexity:

  • Time complexity: O(m + N)
  • Space complexity: O(m + N)

3. Reverse dual Pointers

In method 2, a new sorted array is created to store sorted results, but nums1 has already reserved space in the problem, so we can start sorting from large and put it into nums1’s free area

Complexity:

  • Time complexity: O(m + N)
  • Space complexity: O(1)

AC code

  1. Merge first, sort later

    class solution{
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } Arrays.sort(nums1); }}Copy the code

  2. Double pointer

    class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        int j = 0;
        int[] sorted = new int[nums1.length];

        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                sorted[i + j] = nums1[i++];
            } else{ sorted[i + j] = nums2[j++]; }}if (i < m) {
            while(i < m) { sorted[i + j] = nums1[i++]; }}else {
            while(j < n) { sorted[i + j] = nums2[j++]; }}for (int k = 0; k < m + n; k++) { nums1[k] = sorted[k]; }}}Copy the code

  3. Reverse double pointer

    class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[i + j + 1] = nums1[i--];
            } else {
                nums1[i + j + 1] = nums2[j--]; }}if (i > 0) {
            while (i >= 0) {
                nums1[i + j + 1] = nums1[i--]; }}else {
            while (j >= 0) {
                nums1[i + j + 1] = nums2[j--]; }}}}Copy the code

53. Maximum suborder sum

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Their thinking

Assuming that dp[I] is the largest subsequence ending with NUMs [I] and, thenThe maximum subsequence and Max are the maximum values in the DP array

AC code

public int maxSubArray(int[] nums) {
	//dp[I] represents the maximum subsequence sum ending in nums[I]
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int max = nums[0];

	for (int i = 1; i < nums.length; i++) {
		Nums [I] == nums[I] + nums[I] + nums[I] or nums[I]
		dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
		max = Math.max(dp[i], max);
	}
	return max;
}
Copy the code

26. Remove duplicates from an ordered array

Give you an ordered array nums, ask you to ** * delete the repeated elements, each element appears only once, return the new length of the deleted array.

Example 1:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array NUMs are modified to 0,1,2,3,4. You don't need to worry about the element after the new length in the array.Copy the code

Their thinking

1. Violence (self-inflicted)

For nums[I], find the first number greater than nums[I] and place it at nums[I +1] until no number greater than nums[I] is found. And finally returns I +1, the new length of the array

Complexity:

  • Time complexity: O(n^2)
  • Space complexity: O(1)

2. Double pointer

If there is nums[I] = nums[j], then for I ≤k≤ji \leq k \leq ji≤ K ≤j, there is nums[I] = nums[k] = nums[j], that is, the subscripts of equal elements must be continuous. Space complexity can be reduced to O(n) by maintaining slow and fast Pointers

Complexity:

  • Time complexity: O(n)
  • Space complexity: O(1)

AC code

  1. Violence law

    class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[j] > nums[i]) {
                    nums[i + 1] = nums[j];
                    break;
                }
                if (j == len - 1) {
                    return i+1; }}}returnlen; }}Copy the code

  2. Double pointer

    class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = slow + 1;
        while (fast < nums.length) {
            if (nums[slow] == nums[fast]) {
                do {
                    fast++;
                } while (fast < nums.length && nums[slow] == nums[fast]);
                if (fast == nums.length) {
                    break;
                }
                nums[slow+1] = nums[fast];
                slow++;
            } else{ slow++; fast++; }}return slow + 1; }}Copy the code

  3. Double pointer simple notation

    class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                nums[++i] = nums[j];
            }
        }
        return++i; }}Copy the code