One, and the problem

2020.09.21

No.1 The sum of two numbers

Given an array of integers nums and a target value, find the two integers in the array whose sum is the target value and return their array indices.

You can assume that there is only one answer for each input. However, you cannot use the same element in an array twice.

Example:

Given nums = [2, 7, 11, 15], target = 9

Return [0, 1] because nums[0] + nums[1] = 2 + 7 = 9

Source: LeetCode link: leetcode-cn.com/problems/tw… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=1 lang=javascript * * [1] Sum of two numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    let p1 = 0;  
    while(p1<nums.length) {
        let p2 = nums.length - 1;
        while(p2>0) {
            if(nums[p1] + nums[p2] == target && p1 ! = p2) {return[p1,p2]; } p2--; } p1++; }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=1 lang=javascript * * [1] Sum of two numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    let i = nums.length;
    while(i > 1) {
        let last = nums.pop();
        if (nums.indexOf(target - last) > -1) {
            return [nums.indexOf(target - last), nums.length]
        }
        i--
    }
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=1 lang=javascript * * [1] Sum of two numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
  const map = new Map(a)for (let i = 0; i < nums.length; i ++) {
    const otherIndex = map.get(target - nums[i])
    if(otherIndex ! = =undefined) return [otherIndex, i]
    map.set(nums[i], i)
  }
};
Copy the code

The conventional way to find the sum of two numbers is to sum them one by one to obtain whether the sum satisfies the conditions. Scheme two: can use the stack structure to optimize the access; Scheme 3: Construct a hash table to optimize access

2020.09.22

The sum of three numbers

Given an array of n integers, nums, determine if there are three elements a, b, and c in NUMs such that a + b + c = 0? I want you to find all the triples that satisfy this condition and are not duplicate.

Note: Answers may not contain duplicate triples.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

The set of triples that meet the requirements is: [[-1, 0, 1], [-1, -1, 2]]

Source: LeetCode link: leetcode-cn.com/problems/3s… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=15 lang=javascript * * [15] Sum of three numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var threeSum = function(nums) {
    let r = [];
    // Order from smallest to largest
    nums.sort((a,b) = > a-b);

    if(nums[0] > 0 || nums[nums.length-1] < 0 || nums.length < 3) {
        return [];
    } else {
        for(let i=0; i<nums.length; i++) {let pos = nums[i],
                left = i + 1,
                right = nums.length - 1;
            // Filter to loops where the current item is the same as the previous item
            if(pos == nums[i-1] && i>0) continue;
            while(left < right) {
                let a = nums[left],
                    b = nums[right];
                if(pos + a + b == 0) {
                    r.push([pos,a,b]);
                    // Skip the duplicates in the middle
                    while(left < right && nums[left]==a) left++;
                    while(left < right && nums[right]==b) right--;
                } else if(pos + a + b < 0) {
                    left++;
                } else{ right--; }}}returnr; }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=15 lang=javascript * * [15] Sum of three numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var threeSum = function(nums) {
  let arr = []
  if(nums == null || nums.length < 3) return arr;
  nums.sort((a, b) = > a - b)
  for(var i =0; i<nums.length-2; i++){
    const hashMap = new Map(a)if(nums[i] > 0) break;
    // Remove the reprocessing
    if(i > 0 && nums[i] == nums[i-1]) continue
    for(var j =i+1; j<nums.length; j++){
      const dif = -(nums[i]+nums[j])
      // Remove the reprocessing
      // Since the hashMap is pushed to the array the second time, we need to determine that only three repeats can continue
      if(j>i+2 && nums[j]==nums[j-1] && nums[j]==nums[j-2])
        continue
      if(hashMap.has(dif)){
        arr.push([nums[i],nums[hashMap.get(dif)],nums[j]])
        hashMap.delete(dif)
      }
      hashMap.set(nums[j],j)
    }
  }
  return arr
};
Copy the code

1. Using the quick routing method for reference, fixed pivot, and traversal using left and right Pointers; 2. 2. Traditional hash table is used to optimize efficiency and expand the sum of two numbers

2020.09.23

No.16 the sum of the three nearest numbers

Given an array nums of n integers and a target value. Find the three integers in NUMS so that their sum is closest to target. Returns the sum of these three numbers. Suppose there is only one answer for each set of inputs.

Example:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Description: The closest sum to target is 2 (-1 + 2 + 1 = 2).

Tip:

3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4

Solution:

/* * @lc app=leetcode.cn id=16 lang=javascript * * [16] The sum of the three nearest numbers */

const { lexicographicSortSchema } = require("graphql");

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var threeSumClosest = function(nums, target) {
    // Order from smallest to largest
    nums.sort((a,b) = > a-b);

    if(nums.length>=3) {
        let pivot = 0,
            sum = 0.// r = [],
            r = nums[0] + nums[1] + nums[2];

        for(; pivot<nums.length-2; pivot++) {let left = pivot + 1,
                right = nums.length - 1;
            while(left < right) {
                sum = nums[pivot] + nums[left] + nums[right];
                // You can receive an array of objects and sort them later
                // r.push({
                // value: sum,
                // gap: Math.abs(sum-target)
                // })
                if(Math.abs(sum-target)<Math.abs(r-target)) r = sum;

                if(sum == target){
                    return sum;
                } else if (sum < target) {
                    left++;
                } else if(sum > target) { right--; }}}// return r.sort((a,b) => a.gap-b.gap)[0].value;
        returnr; }};Copy the code

It’s still the extension of the fast array, and it’s the deformation of the sum of three

2020.09.24

The sum of four numbers

Given an array of n integers, nums, and a target, determine if there are four elements a, b, c, and d in NUMS such that a + b + c + d is equal to target. Find all the quads that satisfy the condition and are not duplicate.

Note:

The answer must not contain a repeating quadruple.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

Meet the requirements of the quad sets for: [[- 1, 0, 0, 1], [2, 1, 1, 2], [2, 0, 0, 2]]

Source: LeetCode link: leetcode-cn.com/problems/4s… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=18 lang=javascript * * [18] Sum of four numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function(nums, target) {
    / / sorting
    nums.sort((a,b) = > a-b);

    let r = [];
    
    for(let i = 0; i < nums.length-3; i++ ) {// Remove duplications
        if(i>0 && nums[i-1] == nums[i]) continue;

        for(let j = i+1; j< nums.length - 2; j++ ) {
            // Remove duplications
            if(j>i+1 && nums[j-1] == nums[j]) continue;
            
            let left = j + 1,
                right = nums.length - 1;
            while(left < right) {
                let a = nums[left],
                    b = nums[right];
                if (a+b+nums[i]+nums[j] < target) {
                    left++;
                } else if (a+b+nums[i]+nums[j] > target) {
                    right--;
                } else {
                    r.push([ nums[i], nums[j], nums[left], nums[right] ]);
                    while(left < right && nums[left] == a) {
                        left++
                    };
                    while(left < right && nums[right] == b) { right--; }; }}; }}return r;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=18 lang=javascript * * [18] Sum of four numbers */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function (nums, target) {
  let len = nums.length;
  if (len < 4) return [];
  let ans = [];
  for (let i = 0; i < len - 2; i++) {
    for (let j = i + 1; j < len - 1; j++) {
      let map = {};
      for (let x = j + 1; x < len; x++) {
        let key = target - nums[i] - nums[j] - nums[x];
        if (map[nums[x]]) {
          let temp = [nums[x], ...map[nums[x]]].sort((a, b) = > a - b)
          if(removeDup(ans, temp)) { ans.push(temp); }}else {
          map[key] = [nums[i], nums[j], nums[x]]
        }
      }
    }
  }
  return ans;
}
Copy the code

An enhanced version of the sum of three, with an extra layer of cycling

2020.09.25

No.39 Combination sum

Given an array of candidates with no duplicate elements and a target, find all the combinations in the candidates that can make the sum of the digits as target.

The numbers in the candidates may be selected indefinitely.

Description:

All numbers (including target) are positive integers. The solution set must not contain duplicate combinations. Example 1:

< / c > < / c > candidates = [2,3,6,7]; target = 7;

Input: candidates =,3,5 [2], target = 8, solving sets: [,2,2,2 [2], filling [2], [3, 5]]

Tip:

<= candidates.length <= 30 1 <= candidates.length <= 30 1 <= candidates.length <= 30 1 <= candidates.length <= 30 1 <= target <= 500

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution:

/* * @lc app=leetcode.cn id=39 lang=javascript * * [39] Combined sum */

// @lc code=start
/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
var combinationSum = function(candidates, target) {
    // Sort the array
    candidates.sort((a,b) = > a-b);
    // Simplify invalid elements
    candidates.splice(targetIdx(candidates,target));

    let r = [];

    / / recursion
    function targetDfs(temp ,sum) {
        / / the pruning
        if(sum > target) {
            return;
        } else if (sum == target) {
            r.push(temp.concat())
        }

        for(let i= 0; i<candidates.length; i++) {// The last anchor point
            const p = temp[temp.length-1] | |0;
            // If it is smaller than the last bit, the tree is still traversed at this level. If it is larger than the last bit, the tree needs to search at the next level until the backtrace is terminated
            if(candidates[i] >= p) {
                temp.push(candidates[i]);
                targetDfs(temp, sum + candidates[i]);
                temp.pop()
            }
        }r
    }

    targetDfs([],0);

    return r;
    

    function targetIdx(candidates, target) {
        let index = 0;
        for(let i=0; i<candidates.length; i++) {if(candidates[i] > target) {
                return i;
            } else{ index = i; }}return index + 1; }};Copy the code

The idea is consistent. Traceback, DFS depth-first traversal search, pruning in the appropriate position, using array to achieve the structure of the tree

2020.09.27

No.40 Combination sum – II

Given an array of candidates and a target, find all the combinations in the candidates that can make the totals target.

Each number in the candidates can be used only once in each combination.

Description:

All numbers (including the target number) are positive integers. The solution set must not contain duplicate combinations. Example 1:

Input: candidates =,1,2,7,6,1,5 [10], target = 8, solving sets: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] example 2:

Input: candidates =,5,2,1,2 [2], target = 5, the solution sets: [,2,2 [1], [5]]

Solution a:

/* * @lc app=leetcode.cn id=40 lang=javascript * * [40] Combination sum II */

// @lc code=start
/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
var combinationSum2 = function(candidates, target) {
    // Sort the array from smallest to largest
    candidates.sort((a,b) = > a-b);
    // Simplify arrays
    candidates.splice(targetIdx(candidates, target));

    console.log(candidates);

    let r = [];

    function targetDfs(start,temp,sum) {
        if(sum > target) {
            return;
        } else if(sum == target) {
            r.push(temp.concat());
        }

        for(leti = start; i<candidates.length; i++) {if(candidates[i] == candidates[i-1] && i-1>=start) continue;
            temp.push(candidates[i]);
            targetDfs(i+1,temp,sum+candidates[i]); temp.pop(); }}; targetDfs(0[],0);

    return r;

    function targetIdx(candidates, target) {
        let index = 0;
        for(let i=0; i< candidates.length; i++) {
            if(candidates[i] > target) {
                return i;
            } else{ index = i; }}return index+1; }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=40 lang=javascript * * [40] Combination sum II */

// @lc code=start
/ * * *@param {number[]} candidates
 * @param {number} target
 * @return {number[][]}* /
var combinationSum2 = function (candidates, target) {
  var dp = []
  // solve the order problem (1,2) (2,1)
  candidates.sort((a, b) = > a - b)
  for (let i = 0; i <= target; i++) {
    dp[i] = new Set()
  }
  dp[0].add(' ')
  for (let c of candidates) {
    for (let i = target; i >= c; i--) {
      for (item of dp[i - c]) {
        // Use Set to deduplicate the subitem and convert it to String
        dp[i].add(item + ', ' + c)
      }
    }
  }
  // Turn the Set into an Array
  return Array.from(dp[target]).map(item= > item.slice(1).split(', '))};Copy the code

The first idea is similar to the previous one. You need to have a record of the previous position. You can’t recurse the same element repeatedly. The second idea is to use dynamic programming

2020.09.28

No.53 Maximum suborder sum

Given an array of integers, nums, find a contiguous subarray with the largest sum (the subarray contains at least one element) and return its largest sum.

Example:

Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6. Advanced:

If you already have an O(n) solution, try a more sophisticated diet-and-conquer solution.

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=53 lang=javascript * * [53] maximum suborder and */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function(nums) {
    let max = nums[0], 
        cache = 0;
    for(let i=0; i< nums.length; i++) {
        cache = Math.max(cache+nums[i],nums[i]);
        max = Math.max(cache,max);
    }
    return max;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=53 lang=javascript * * [53] maximum suborder and */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
function Status(l, r, m, i) {
    this.lSum = l;
    this.rSum = r;
    this.mSum = m;
    this.iSum = i;
}

const pushUp = (l, r) = > {
    const iSum = l.iSum + r.iSum;
    const lSum = Math.max(l.lSum, l.iSum + r.lSum);
    const rSum = Math.max(r.rSum, r.iSum + l.rSum);
    const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
    return new Status(lSum, rSum, mSum, iSum);
}

const getInfo = (a, l, r) = > {
    if (l === r) {
        return new Status(a[l], a[l], a[l], a[l]);
    }
    const m = (l + r) >> 1;
    const lSub = getInfo(a, l, m);
    const rSub = getInfo(a, m + 1, r);
    return pushUp(lSub, rSub);
}

var maxSubArray = function(nums) {
    return getInfo(nums, 0, nums.length - 1).mSum;
};
Copy the code

F (n)= Max {f(n-1)+ai,ai}; f(n)= Max {f(n-1)+ai,ai}; The second idea is to use divide and conquer, divide the array into two segments, each segment as long as the largest is the largest, when you get to the last back, the final sum is the maximum

2020.09.29

No.64 Minimum path sum

Given an m x N grid containing non-negative integers, find a path from the top left to the bottom right that minimizes the sum of numbers on the path.

Note: You can only move down or to the right one step at a time.

Example:

,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum.

Source: LeetCode link: leetcode-cn.com/problems/mi… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution:

/* * @lc app=leetcode.cn id=64 lang=javascript * * [64] minimum path and */

// @lc code=start
/ * * *@param {number[][]} grid
 * @return {number}* /
var minPathSum = function(grid) {
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (i == 0 && j == 0) {
                // The entry is not processed
                grid[i][j] = grid[i][j];
            } else if (i == 0 && j > 0) {
                // The first row of elements
                grid[i][j] += grid[i][j - 1];
            } else if (i > 0 && j === 0) {
                // The first column element
                grid[i][j] += grid[i - 1][j];
            } else {
                / / recurrence formula grid [I] [j] = min {grid [I] [1], the grid [j] [I - 1]}
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); }}}return grid[grid.length - 1][grid[0].length - 1];
};
Copy the code

In classical dynamic programming, the recursive cyclic invariant is grid[I][j] = min{grid[I][J-1], grid[i-1][J]}, and the boundary details need to be paid attention to

2020.09.30

No.167 Sum of two numbers II – Enter an ordered array

Given an ordered array arranged in ascending order, find two numbers such that their sum equals the target number.

The function should return the two subvalues index1 and index2, where index1 must be less than index2.

Description:

The returned subindex values (index1 and index2) do not start from zero. You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements. Example:

Input: numbers = [2, 7, 11, 15], target = 9 output: [1,2] explanation: the sum of 2 and 7 equals the target number 9. So index1 = 1, index2 = 2.

Solution a:

/* * @lc app=leetcode.cn id=167 lang=javascript * * [167] Sum of two numbers II - Input ordered array */

// @lc code=start
/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(numbers, target) {
    let p1 = 0,
        p2 = numbers.length -1;
    while(p1<p2) {
        if(numbers[p1]+numbers[p2]<target) {
            p1++;
        } else if(numbers[p1]+numbers[p2]>target) {
            p2--;
        } else {
            return [p1+1,p2+1]}}};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=167 lang=javascript * * [167] Sum of two numbers II - Input ordered array */

// @lc code=start
/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(numbers, target) {
    let map = {}
    for(let i = 0; i < numbers.length; i ++) {
        const dim = target - numbers[i]
        if(map[dim] === undefined) {
            map[numbers[i]] = i
        }else {
            return [map[dim] + 1,i + 1]}}};Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=167 lang=javascript * * [167] Sum of two numbers II - Input ordered array */

// @lc code=start
/ * * *@param {number[]} numbers
 * @param {number} target
 * @return {number[]}* /
var twoSum = function (numbers, target) {
  let len = numbers.length,
    left = 0,
    right = len - 1,
    mid = 0
  for (let i = 0; i < len; ++i) {
    left = i + 1
    while (left <= right) {
      mid = parseInt((right - left) / 2) + left
      if (numbers[mid] == target - numbers[i]) {
        return [i + 1, mid + 1]}else if (numbers[mid] > target - numbers[i]) {
        right = mid - 1
      } else {
        left = mid + 1}}}return [-1, -1]}Copy the code

There are three solutions: 1. The double pointer gathers toward the middle; 2. 2. Construct a map data structure; 3, binary search

2020.10.01

No.216 Combination Aggregate III

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate numbers in each combination.

Description:

All numbers are positive integers. The solution set must not contain duplicate combinations. Example 1:

Input: k = 3, n = 7 output: [[1,2,4]] example 2:

Input: k = 3, n = 9 output: [[1,2,6], [1,3,5], [2,3,4]

Solution a:

/* * @lc app=leetcode.cn id=216 lang=javascript * * [216] Combination sum III */

// @lc code=start
/ * * *@param {number} k
 * @param {number} n
 * @return {number[][]}* /
var combinationSum3 = function(k, n) {
    let r = [];

    function sumDfs(start, temp, sum) {
        if(temp.length == k) {
            if(sum == n) {
                r.push(temp.concat());
            };
            return;
        }
        for(leti=start; i<=9; i++) { temp.push(i); sumDfs(i+1,temp,sum+i); temp.pop(); }}; sumDfs(1[],0);
    
    return r;
    
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=216 lang=javascript * * [216] Combination sum III */

// @lc code=start
/ * * *@param {number} k
 * @param {number} n
 * @return {number[][]}* /
var combinationSum3 = function(k, n) {
    let temp = [];
    const ans = [];
    const check = (mask, k, n) = > {
        temp = [];
        for (let i = 0; i < 9; ++i) {
            if ((1 << i) & mask) {
                temp.push(i + 1); }}return temp.length === k && temp.reduce((previous, value) = > previous + value, 0) === n;
    }

    for (let mask = 0; mask < (1 << 9); ++mask) {
        if(check(mask, k, n)) { ans.push(temp); }}return ans;
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=216 lang=javascript * * [216] Combination sum III */

// @lc code=start
/ * * *@param {number} k
 * @param {number} n
 * @return {number[][]}* /
var combinationSum3 = function(k, n) {
    let number = [[]];
    let a = []
    let numbers = [1.2.3.4.5.6.7.8.9];
    for(let i = 0; i < 9; i++){
        let turn = number.map(v= > [...v,numbers[i]])
        // console.log(turn)
        number = number.concat(turn);
    }
    for(let i = 0; i < number.length; i++){
        if(number[i].length ! = k){continue;
        }else{
            if(sum(number[i])! ==n){continue;
            }else{
                a.push(number[i])
            }
        }
    }
    return a;
};
function sum(arr){
    let sum = 0;
    for(let i = 0; i < arr.length; i++){
        sum+=arr[i];
    }
    return sum;
}
Copy the code

Three solutions: 1. Classical backtracking algorithm to construct DFS query; 2. 2. SAO operation, using binary mask for shift enumeration; 3. Construct a map data structure

2020.10.04

No.689 The largest sum of three non-overlapping subarrays

Given the array NUMs consists of positive integers, find the largest sum of three nonoverlapping subarrays.

Each subarray is of length k, and we want to maximize the sum of these 3 times k items.

Returns a list of starting indexes for each interval (index starting from 0). If there are multiple results, return the one with the smallest lexicographical order.

Example:

,2,1,2,6,7,5,1 input: [1], 2 output: [0, 3, 5] : subarray [1, 2], [2, 6], [7, 5) corresponding to the leading index for [0, 3, 5]. We can also take [2, 1], but the result [1, 3, 5] is lexicographically larger. Note:

Nums. length ranges from [1, 20000]. Nums [I] ranges from [1, 65535]. K is in the range [1, floor(nums.length / 3)].

Solution a:

/* * @lc app=leetcode.cn id=689 lang=javascript * * [689] Maximum sum of three non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number[]}* /
var maxSumOfThreeSubarrays = function(nums, k) {
    const dp = new Array(nums.length).fill(0).map( _= > new Array(4).fill(0));// Calculate the prefix and
    const prefixSums=[nums[0]].for(let i=1; i<nums.length; i++) { prefixSums[i] = prefixSums[i-1] + nums[i];
    }
    // Populate the dp array
    for(let n=1; n<=3; n++) {for(let i=k*n-1; i<nums.length; i++) {const prev1 = i-1> =0 ? dp[i-1][n] : 0;
        const prevK = i-k >= 0 ? dp[i-k][n-1] : 0;
        const tailSum = i-k >= 0 ? prefixSums[i] - prefixSums[i-k] : prefixSums[i];
        dp[i][n] = Math.max(prev1, prevK + tailSum); }};// Find the least lexicographical solution according to the dp array
    const result = [];
    let n = 3;
    let current = dp.length-1;
    while(result.length < 3) {
      const v = dp[current][n];
      let i = current;
      while( i-1> =0 && dp[i-1][n] == v) {
        i--;
      }
      current = i - k + 1;
      result.push(current);
      current--;
      n--;
    }
    
    return result.reverse();
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=689 lang=javascript * * [689] Maximum sum of three non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number[]}* /
var maxSumOfThreeSubarrays = function(nums, k) {
    let n = nums.length
    let l = n - k + 1
    let sums = Array(l).fill(0)
    let s = nums.slice(0,k).reduce((x,y) = > x+y)
    sums[0] = s
    for (let i=1; i<l; i++){ s = s + nums[i-1+k] - nums[i-1]
        sums[i] = s
    }
    let j,m
    let mid = new Map(a)for (let i=k-1; i<l; i++){ mid.set(i,0)}for (leti=k; i<l; i++){ j = mid.get(i-1)
        if (sums[i-k] > sums[j]){
            j = i-k
        }
        mid.set(i,j)
    }
    let right = new Map(a)for (let i=2*k-1; i<l; i++){ right.set(i,k) }let res = [0,k,2*k]
    for (let r=2*k; r<l; r++){ m = right.get(r-1)
        if (sums[r-k]+sums[mid.get(r-k)] > sums[m]+sums[mid.get(m)]){
            m = r-k
        }
        right.set(r,m)
        if (sums[r]+sums[m]+sums[mid.get(m)] > sums[res[0]]+sums[res[1]]+sums[res[2]]){
            res = [mid.get(m),m,r]
        }
    }
    return res
};
Copy the code

Two solutions: Dp [I][n]= Max {dp[i-1][n], dp[i-k][n-1]+sumRange(i-k+1, I)}, dp[I][n]= Max {dp[i-1][n], dp[i-k][n-1]+sumRange(i-k+1, I)} The contiguous interval of n numbers is k; 2. Segment the array to the left, middle and right, and then move to get the maximum value

2020.10.05

No.1031 The largest sum of two nonoverlapping subarrays

Given an array of non-negative integers A, return the maximum sum of the elements in two non-overlapping (contiguous) subarrays of length L and M. (To be clear, a subarray of length L can appear before or after a subarray of length M.)

V = (A[I] + A[I +1] +… + A[i+L-1]) + (A[j] + A[j+1] + … + A[J + m-1]) and satisfies one of the following conditions:

0 <= I < I + L-1 < j < j + m-1 < a.length, or 0 <= j < j + m-1 < I < I + L-1 < a.length.

Example 1:

Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 output: 20 Example 2:

Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 output: 29 Example 3:

Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 output: 31

Tip:

L >= 1 M >= 1 L + M <= A.length <= 1000 0 <= A[i] <= 1000

Solution a:

/* * @lc app=leetcode.cn id=1031 lang=javascript * * [1031] Maximum sum of two non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}* /
var maxSumTwoNoOverlap = function(A, L, M) {
    let max = -Infinity,
        lArr = sum(L), // Get the sum array of L
        mArr = sum(M); // Get the sum array of M

    for(let i=0; i<lArr.length; i++) {for(let j=0; j<mArr.length; j++) {if( j > i+L-1 || i> j+M-1 ) {
                max = Math.max(max, lArr[i]+mArr[j]); }}}return max;

    function sum(n) {
        let s = [];
        for(let i=0; i+n<=A.length; i++) { s.push(A.slice(i,i+n).reduce((prev,curr) = >prev+curr))
        }
        returns; }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=1031 lang=javascript * * [1031] Maximum sum of two non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}* /
var ListNode = function (val, start, end) {
    this.val = val;
    this.start = start;
    this.end = end;
    this.prev = null;
    this.next = null;
}

var List = function () {
    this.head = null; 
    this.tail = null;
}
var maxSumTwoNoOverlap = function(A, L, M) {
    let l = [], m = [];
    let lList = new List();
    for (let i = 0; i <= A.length-L; i++) {
        let sum = 0;
        for (let j = 0; j < L; j++) {
            sum+= A[i+j];
        }
        let node = new ListNode(sum, i, i+L-1);   
        addToList(lList,node);
    }
    
    let mList = new List();
    for (let i = 0; i <= A.length-M; i++) {
        let sum = 0;
        for (let j = 0; j < M; j++) {
            sum+= A[i+j];
        }
        let node = new ListNode(sum, i, i+M-1); 
        addToList(mList, node);
    }
    
    let mPtr = mList.head;
    let lPtr = lList.head;
    let max = 0;
   
    mPtr = mList.head;
    while (mPtr) {
        while (lPtr) {
           if (Math.max(mPtr.start, lPtr.start) <= Math.min(mPtr.end, lPtr.end)) {
                lPtr = lPtr.next;
            } else {
                max = Math.max(max, mPtr.val+ lPtr.val);
                lPtr = lPtr.next;
            } 
        }
        mPtr = mPtr.next;
        lPtr= lList.head;
    }
  return max;
  
};

function addToList(list, node) {
    if(! list.head) { list.head= node; list.tail = node; }else {
        if (list.head.val <= node.val) {
            list.head.prev = node;
            node.next = list.head;
            list.head = node;
        } else if (list.tail.val >= node.val) {
            list.tail.next = node;
            node.prev = list.tail;
            list.tail = node;
        } else {
            let ptr = list.head;
            while(ptr && ptr.val > node.val) {
                ptr= ptr.next;
            }
            if(! ptr) { list.tail = node; list.head.next = list.tail; node.prev = list.tail; }else {
                letprev = ptr.prev; prev.next = node; node.prev = prev; node.next = ptr; ptr.prev = node; }}}}Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=1031 lang=javascript * * [1031] Maximum sum of two non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}* /
var maxSumTwoNoOverlap = function(A, L, M) {
    return Math.max(traverse(L,M), traverse(M,L));
    
    function traverse(a, b) {
        let res = 0;
        for (let i = 0; i <= A.length-a-b; i++) {
            let sum = A.slice(i,i+a+b).reduce((acc,cur) = > acc+cur);
            let l = i+a, r = l+b;
            res = Math.max(res, sum);
            while (r < A.length) {
                sum = sum-A[l]+A[r];
                res = Math.max(res, sum) l++, r++; }}returnres; }};Copy the code

Plan 4:

/* * @lc app=leetcode.cn id=1031 lang=javascript * * [1031] Maximum sum of two non-overlapping subarrays */

// @lc code=start
/ * * *@param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}* /
var maxSumTwoNoOverlap = function(A, L, M) {
    let len = A.length;
    for(let i = 1; i < len; i++) {
        A[i] += A[i - 1];
    }
    
    let LMax = A[L - 1], MMax = A[M-1];
    let res = A[M + L - 1];
    for(let i = M + L ; i< len ; i++) {
        // update LMax to i - M; 
        LMax = Math.max(LMax, A[i - M ] - A[i - M - L]);
        MMax = Math.max(MMax, A[i - L ] - A[i - M - L]);
        res = Math.max(res,
            LMax + A[i] - A[i - M],
            MMax + A[i] - A[i - L]
        )
    }
    return res;
};
Copy the code

There are three solutions: 1. Get the sum of all prefixes before M and L, pair and filter the sum to get the maximum value; 2. 2. Construct two-way linked list data structure; 3, use the moving window for selection; 4, dynamic programming, recursive approximation res = Max {res, the maximum sum of M, the maximum sum of L}

2020.10.16

No.1013 divides the array into three equal parts

Give you an array of integers A, return true only if you can divide it into three equal non-empty parts, otherwise return false.

Formally, if you can find the index I +1 < j and A[0] + A[1] +… + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[a.length-1] to triplize an array.

Example 1:

Input: [0,2,1,-6,6,-7,9,1,2,0,1] Output: True Explanation: 0 + 2 + 1 = -6 + 6-7 + 9 + 1 = 2 + 0 + 1

Input: [0,2,1,-6,6,7,9,-1,2,0,1] output: false example 3:

Input: [3,3,6,5,-2,2,5,1,-9,4] Output: True Description: 3 + 3 = 6 = 5-2 + 2 + 5 + 1-9 + 4

Tip:

3 <= A.length <= 50000 -10^4 <= A[i] <= 10^4

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=1013 lang=javascript * * [1013] Divide the array into three equal parts */

// @lc code=start
/ * * *@param {number[]} A
 * @return {boolean}* /
var canThreePartsEqualSum = function(A) {
    const sum = A.reduce((prev, memo) = > prev + memo);
    if( sum % 3! =0 ) {
        return false;
    } else {
        const s = sum / 3;
        // Left and right Pointers
        let p1 = 0,
            l = 0,
            p2 = A.length - 1,
            r = 0;
        
        while( p1 < A.length ) {
            l += A[p1];

            if(l ! = s) { p1++; }else {
                break; }}while( p2 > 0 ) {
            r += A[p2];
            if(r ! = s) { p2--; }else {
                break; }}if( p1 + 1 < p2 ) {
            return true;
        } else {
            return false; }}};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=1013 lang=javascript * * [1013] Divide the array into three equal parts */

// @lc code=start
/ * * *@param {number[]} A
 * @return {boolean}* /
var canThreePartsEqualSum = function(A) {
    const sum = A.reduce((prev, memo) = > prev+memo);
    if(sum % 3! =0) {
        return false;
    } else {
        const s = sum / 3;
        let temp = 0.// Used to record the sum of the preceding I entries
            n = 0; // To record the number of cut points
        for(let i=0; i< A.length; i++) {
            temp += A[i];
            if(temp == s) {
                n++;
                temp = 0;
            };

            if(n == 3) return true;
        };

        return false; }};Copy the code

There are two solutions: 1. Compare the position of the left and right Pointers, which can be synthesized into a loop, but it is not easy to expand, and can be converted into a comparison of the position of the pointer to return the result for more parts of the problem; 2. 2. Record the number of segmentation points, so that problems divided into more parts can be better extended, and the results can be returned by judging the number of points

Conclusion:

And the common practice is to use map, hash, stack and other data structures to optimize the processing, followed by the use of left and right pointer reduction to carry out the number of cycles;

A common solution to subproblems is to use dynamic programming and backtracking pruning to deal with optimization

Second, the position index problem

2020.10.09

No.34 looks for the first and last position of an element in the sorted array

Given an array of ascending integers, nums, and a target value. Find the start and end positions in the array for the given target value.

Your algorithm has to be order log n in time.

Return [-1, -1] if no target value exists in the array.

Example 1:

Input: nums =,7,7,8,8,10 [5], target = 8 output: [3, 4] example 2:

Nums = [5,7,7,8,8,10], target = 6 output: [-1,-1]

Source: LeetCode link: leetcode-cn.com/problems/fi… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=34 lang=javascript * * [34] Find the first and last position of an element in a sorted array */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var searchRange = function(nums, target) {
    let p1 = 0,
        p2 = nums.length - 1;
    
    // Binary search
    while(p1 <= p2) {
        let mid = Math.floor((p1 + p2) / 2);
        
        if( target < nums[mid] ) {
            p2 = mid - 1;
        } else if( target > nums[mid] ) {
            p1 = mid + 1;
        } else {
            p1 = mid;
            p2 = mid;
            break; }};/ / determine
    if( p1 > p2 ) {
        return [-1, -1];
    } else {
        // Push it from the center to the two farthest targets
        while(nums[p1-1] == target) p1--;
        while(nums[p2+1] == target) p2++;
        return[p1,p2]; }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=34 lang=javascript * * [34] Find the first and last position of an element in a sorted array */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var searchRange = function(nums, target) {
    // console.log(nums.indexOf(target),nums.lastIndexOf(target))
    return [nums.indexOf(target),nums.lastIndexOf(target)]
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=34 lang=javascript * * [34] Find the first and last position of an element in a sorted array */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var searchRange = function(nums, target) {
  return nums.map(n= > n - target).reduce((p, n, i) = > {
    if (n === 0) {
       if (p[0] = = = -1) {
         p[0] = i
         p[1] = i
       }
       p[1] = i
    }
    return p
  }, [-1, -1])};Copy the code

There are three solutions: 1, binary search: receive the middle back to both sides of the extension to the farthest position is the first and last search position; 2. Use the API of indexOf and lastIndexOf; 3. Problem transformation: convert the position into the difference between the target value and traversal position value, and use the Reduce function to find the difference value

2020.10.10

No.35 search for insertion position

Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the order in which it will be inserted.

You can assume that there are no duplicate elements in the array.

Example 1:

Input: [1,3,5,6], 5 output: 2 example 2:

Input: [1,3,5,6], 2 Output: 1 Example 3:

Input: [1,3,5,6], 7 output: 4 example 4:

Input: [1,3,5,6], 0 output: 0

Source: LeetCode link: leetcode-cn.com/problems/se… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=35 lang=javascript * * [35] Search insert location */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function(nums, target) {
    for(let i=0; i<nums.length; i++) {
        if(nums[i] == target) {
            return i;
        } else {
            if(nums[i] < target && nums[i+1] > target) {
                return i+1;
            };
            if(nums[nums.length - 1] < target) return nums.length;
            if(nums[0] > target) return 0; }}};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=35 lang=javascript * * [35] Search insert location */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function(nums, target) {
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1; }}return ans;
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=35 lang=javascript * * [35] Search insert location */

// @lc code=start
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var searchInsert = function(nums, target) {
    return nums.concat(Infinity).findIndex(n= > n >= target);
};
Copy the code

There are three solutions: 1. Conventional solution: direct traversal comparison, return the position according to the condition, the time complexity is O(N); 2, binary search, the optimization of the first solution, using binary search, reduce the space-time complexity to O(logN); 3. Use js apis such as findIndex and sort to search

2020.10.12

No.162 looking for spikes

A peak element is an element whose value is greater than the adjacent values.

Given an input array nums, where nums[I] ≠ nums[I +1], find the peak element and return its index.

The array may contain more than one peak, in which case, just return the location of any one peak.

You can assume that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1] output: 2 description: 3 is the peak element, and your function should return its index 2. Example 2:

Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5 Explanation: Your function may return index 1, whose peak element is 2; Or return index 5 with a peak element of 6. Description:

Your solution should be order logN time.

Solution a:

/* * @lc app=leetcode.cn id=162 lang=javascript * * [162] Find peak */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var findPeakElement = function(nums) {
    let p1 = 0,
        p2 = nums.length - 1;

    // Binary search
    while( p1 < p2 ) {
        let mid = Math.floor( (p1 + p2) / 2 );
        if( nums[mid] > nums[mid+1] ) {
            p2 = mid;
        } else {
            p1 = mid + 1; }};return p2;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=162 lang=javascript * * [162] Find peak */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var findPeakElement = function(nums) {
    return nums.indexOf(Math.max(... nums)); };Copy the code

There are two ways to solve this problem: 1. Binary search. Consider binary search when you see that it requires O(logN). Use the indexOf and Math.max apis

2020.10.13

No.724 looks for the central index of the array

Given an array nums of type integer, write a method that returns the “central index” of the array.

We define an array central index in such a way that the sum of all the elements to the left of the array central index is equal to the sum of all the elements to the right.

If the array does not have a central index, then we should return -1. If the array has multiple central indexes, we should return the one closest to the left.

Example 1:

Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Description: The sum of the numbers to the left of index 3 (NUMs [3] = 6) (1 + 7 + 3 = 11) is the same as the sum of the numbers to the right (5 + 6 = 11). 3 was also the first central index to meet the requirements. Example 2:

Input: nums = [1, 2, 3] Output: -1 Description: There is no central index in the array that meets this condition.

Description:

The numS length ranges from 0 to 10000. Any nums[I] will be an integer in the range [-1000, 1000].

Solution a:

/* * @lc app=leetcode.cn id=724 lang=javascript * * [724] Find the central index of the array */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var pivotIndex = function(nums) {
    // Return -1 if null
    if(nums.length == 0) return -1;

    / / the first
    if(aSum(nums.slice(1)) = =0) return 0;
    
    / / in the middle
    for(let i=1; i<= nums.length-2; i++) {if(aSum(nums.slice(0,i)) == aSum(nums.slice(i+1))) return i
    };

    // The last one
    if(aSum(nums.slice(0,nums.length-1)) = =0) return nums.length - 1;

    return -1;

    function aSum(arr) {
        return arr.reduce((prev, memo) = > prev + memo, 0); }};Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=724 lang=javascript * * [724] Find the central index of the array */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var pivotIndex = function(nums) {
    let sum = nums.reduce((prev, memo) = > prev+memo,0),
        leftsum = 0;
    
    for(let i=0; i<nums.length; i++) {if(sum - nums[i] == 2* leftsum) {
            return i;
        } else{ leftsum += nums[i]; }}return -1;

};
Copy the code

There are two solutions: 1. Use the API of Reduce to calculate the sum of the left and the right respectively, and then make a comparison. Here, we need to process the first and the last. 2, for 1, we find that the sum = left and + nums[I] + right sum, and when the sum of left is equal to the sum of right, the sum -nums [I] = 2* left sum, then we do not need to sum, simplify the middle layer of iterating, so the space-time complexity is O(N).

2020.10.14

No.747 is at least twice the maximum of the other numbers

In a given array nums, there is always a maximum element.

Finds whether the largest element in the array is at least twice the size of each other number in the array.

If so, the index of the largest element is returned, otherwise -1 is returned.

Example 1:

Input: nums = [3, 6, 1, 0] Output: 1 Explanation: 6 is the maximum integer, for the other integers in the array, 6 is greater than twice the other elements in the array. The index of 6 is 1, so we return 1.

Example 2:

Input: nums = [1, 2, 3, 4] Output: -1 Description: 4 is not more than twice the size of 3, so we return -1.

Tip:

Nums are in the range of [1], 50]. Each nums[I] is in the range of [0], 100].

Source: LeetCode link: leetcode-cn.com/problems/la… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=747 lang=javascript * * [747] Maximum number that is at least twice any other number */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var dominantIndex = function(nums) {
    let max = -Infinity, pos = 0;
    for(let i=0; i< nums.length; i++) {
        if( nums[i] > max) { max = nums[i]; pos = i; }}for(let i=0; i< nums.length; i++) {
        if( i ! = pos && (2*nums[i] ) > max) return -1;
    }
    return pos;
};
Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=747 lang=javascript * * [747] Maximum number that is at least twice any other number */

// @lc code=start
/ * * *@param {number[]} nums
 * @return {number}* /
var dominantIndex = function(nums) {
    let max = 0, max2 = 0, pos = 0;
    for(let i = 0; i< nums.length; i++) {
        if(nums[i] > max) {
            max2 = max;
            max = nums[i];
            pos = i
        } else if(nums[i] > max2) { max2 = nums[i]; }};if(2*max2 > max) return -1;

    return pos;
};
Copy the code

There are two schemes: 1, two times of loop, the first time to obtain the maximum, the second time to compare whether to meet the condition, the time complexity of O(N)+O(N) ~ O(N); 2, a loop, get the first and second largest, return results only need to compare whether the second largest satisfies the condition, time complexity O(N)

2020.10.15

No.852 peak index of the array of mountains

We call an array A that matches the following properties A mountain:

A.length >= 3 0 < I < a.length-1 causes A[0] < A[1] <… A[i-1] < A[i] > A[i+1] > … > A[a.length-1] returns any array where A[0] < A[1] <… A[i-1] < A[i] > A[i+1] > … > the value of I for A[a.length-1].

Example 1:

Input: [0,1,0] output: 1 example 2:

Input: [0,2,1,0] output: 1

Tip:

3 <= a.length <= 10000 0 <= A[I] <= 10^6 A is the mountain range as defined above

Source: LeetCode link: leetcode-cn.com/problems/pe… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Solution a:

/* * @lc app=leetcode.cn id=852 lang=javascript * * [852] Mountain array peak index */

// @lc code=start
/ * * *@param {number[]} arr
 * @return {number}* /
var peakIndexInMountainArray = function(arr) {
    return arr.indexOf(Math.max(... arr)); };Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=852 lang=javascript * * [852] Mountain array peak index */

// @lc code=start
/ * * *@param {number[]} arr
 * @return {number}* /
var peakIndexInMountainArray = function(arr) {
    let max = -Infinity, pos = 0;
    for(let i=0; i<arr.length; i++) {
        if(arr[i] > max) { max = arr[i]; pos = i; }};return pos;
};
Copy the code

Solution 3:

/* * @lc app=leetcode.cn id=852 lang=javascript * * [852] Mountain array peak index */

// @lc code=start
/ * * *@param {number[]} arr
 * @return {number}* /
var peakIndexInMountainArray = function(arr) {
    let l = 0, r = arr.length - 1;
    // Binary search
    while( l < r ) {
        let m = Math.floor( ( l + r ) / 2 );
        if( arr[m] < arr[m+1] ) {
            l = m + 1;
        } else{ r = m; }};return l;
};
Copy the code

There are three options: 1. Use the indexOf and Math. Max apis; 2. 2. Loop again to obtain the maximum value and position information; 3, using binary search, can reduce the time complexity to O(logN)

Conclusion:

The common practice of location index is to use the API of indexOf and lastIndexOf to find the location, and different requirements in the middle can be converted into different formulas for processing.

The essence of the location index problem is a search problem, which can be deformed by common search algorithms, but it needs to consider the mutual exclusion of the complexity of space and time. The most common search algorithm is binary search algorithm

Front – end common algorithm (array article)– on

One, and the problem

2020.09.21

No.1 The sum of two numbers

Solution a:

Scheme 2:

Solution 3:

2020.09.22

The sum of three numbers

Solution a:

Scheme 2:

2020.09.23

No.16 the sum of the three nearest numbers

Solution:

2020.09.24

The sum of four numbers

Solution a:

Scheme 2:

2020.09.25

No.39 Combination sum

Solution:

2020.09.27

No.40 Combination sum – II

Solution a:

Scheme 2:

2020.09.28

No.53 Maximum suborder sum

Solution a:

Scheme 2:

2020.09.29

No.64 Minimum path sum

Solution:

2020.09.30

No.167 Sum of two numbers II – Enter an ordered array

Solution a:

Scheme 2:

Solution 3:

2020.10.01

No.216 Combination Aggregate III

Solution a:

Scheme 2:

Solution 3:

2020.10.04

No.689 The largest sum of three non-overlapping subarrays

Solution a:

Scheme 2:

2020.10.05

No.1031 The largest sum of two nonoverlapping subarrays

Solution a:

Scheme 2:

Solution 3:

Plan 4:

2020.10.16

No.1013 divides the array into three equal parts

Solution a:

Scheme 2:

Conclusion:

Second, the position index problem

2020.10.09

No.34 looks for the first and last position of an element in the sorted array

Solution a:

Scheme 2:

Solution 3:

2020.10.10

No.35 search for insertion position

Solution a:

Scheme 2:

Solution 3:

2020.10.12

No.162 looking for spikes

Solution a:

Scheme 2:

2020.10.13

No.724 looks for the central index of the array

Solution a:

Scheme 2:

2020.10.14

No.747 is at least twice the maximum of the other numbers

Solution a:

Scheme 2: