This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic describes

This is 611 on LeetCode. The number of valid triangles, of medium difficulty.

Tag: sort, dichotomy, double pointer

Given an array of non-negative integers, your task is to count the number of triples that make up the three sides of a triangle.

Example 1:

Input: [2,2,3,4] Output: 3 Explanation: The valid combination is: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3Copy the code

Note:

  1. The array length does not exceed 1000.
  2. The range of integers in the array is 0, 1000.

Fundamental analysis

According to the passage, we should count all the matches
n u m s [ k ] + n u m s [ j ] > n u m s [ i ] nums[k] + nums[j] > nums[i] Triple of conditions
( k . j . i ) (k,j,i) The number of.

In order to prevent the statistics of repeated triples, we can first sort the array, and then adopt the strategy of “enumerate the larger number first; find the larger number in the subscript not more than the larger number; find the smaller number in the subscript not more than the larger number.”

Sort + violence enumeration

Based on the “basic analysis”, we can easily write an implementation of “sort + three-level loop”.

Code:

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                for (int k = j - 1; k >= 0; k--) {
                    if(nums[j] + nums[k] > nums[i]) ans++; }}}returnans; }}Copy the code
  • Time complexity: the sorting time complexity is O(nlog⁡n)O(n\log{n})O(nlogn); The three-level traversal to find all the ternary ancestors is O(n3)O(n^3)O(n3). The overall complexity is O(n3)O(n^3)O(n3).
  • O(log⁡n)O(\log{n})O(logn)

Sort + dichotomy

Based on the basic idea of optimizing enumerations that we discussed earlier, to find a triple that fits a condition, one of the pointcuts could be “enumerate two of the values in the triple and then optimize the logic for finding the third number.”

We find that when the enumeration reaches the larger index III and the smaller index JJJ under the premise of an ordered array, In [[0, 0, j) j) within the scope of [0, j) to find the accord with nums’ [k] + nums [j] > nums [I] nums [k ‘] + nums [j] > nums nums [I] ‘[k] + nums [j] > nums [I] condition of k’ k ‘k’ collection, The number line with the smallest subscript conforming to the conditions KKK as the dividing point has “binarity”.

If nums[I]nums[I]nums[I]nums[I]nums[I]nums[I]nums[I]nums[j]nums[J]nums[J]nums[J]nums[J] [J]nums[J]

  • Nums [j]>nums[I]nums[k’] +nums[j]>nums[I]nums[k’] +nums[j]>nums[I]nums[k’] +nums[j]>nums[I];
  • Nums [I]nums[k’] +nums[j]>nums[I]nums[k’] +nums[j]>nums[I]nums[k’] +nums[j]>nums[I].

Therefore, we can find the segmentation point KKK by “dichotomy”. In the range of [k,j)[k,j)[k,j), that is, the number of k’k ‘ ‘k ‘ ‘meeting the condition when JJJ and III are fixed.

Code:

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int l = 0, r = j - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (nums[mid] + nums[j] > nums[i]) r = mid;
                    else l = mid + 1;
                }
                if(l == r && nums[r] + nums[j] > nums[i]) ans += j - r; }}returnans; }}Copy the code
  • Time complexity: the sorting time complexity is O(nlog⁡n)O(n\log{n})O(nlogn); The complexity of a two-level traversal plus a dichotograph of all eligible triples is O(n2∗log⁡n)O(n^2*\log{n})O(n2∗logn). The overall complexity is O(n2∗log⁡n)O(n^2*\log{n})O(n2∗logn)
  • O(log⁡n)O(\log{n})O(logn)

Sort + double pointer

Further, we find that when we enumerate the larger index iii and find the lower index JJJ in the range of [0, I)[0, I)[0, I)[0, I) (because the array is ordered, that is, gradually reducing the value), Nums [k]+nums[j]>nums[I]nums[k]+nums[j]>nums[I]+nums[j]>nums[I]+nums[j]>nums[I]

Therefore, we can enumerate JJJ in the range of [0, I)[0, I)[0, I)[0, I) by means of double pointer in the range of [0, I) by gradually reducing the subscript, and increase the subscript of KKK when it meets the KKK that does not meet the condition, so as to find the number of all triples that meet the condition.

Code:

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1, k = 0; k < j; j--) {
                while(k < j && nums[k] + nums[j] <= nums[i]) k++; ans += j - k; }}returnans; }}Copy the code
  • Time complexity: the sorting time complexity is O(nlog⁡n)O(n\log{n})O(nlogn), and the double pointer to find all matching triples is O(n2)O(n^2)O(n2). The overall complexity is O(n2)O(n^2)O(n2).
  • O(log⁡n)O(\log{n})O(logn)

The last

This is the 611 article in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.