AC第三天

1.两数之和II-输入有序数组

双向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class LeetCode6Test {
    @Test
    public void test() {
        int[] numbers = {-1, 0};
        int target = -1;
        System.out.println(Arrays.toString(twoSum(numbers, target)));
    }

    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int s = numbers[left] + numbers[right];
            if (s == target) {
                break;
            } else if (s < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{left + 1, right + 1};
    }
}

2.三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode7Test {
    @Test
    public void test() {
        int[] numbers = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(numbers));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;  // 跳过重复的i
            }
            if (nums[i] + nums[i+1] + nums[i+2] > 0) {
                break;  // 最小的三个数之和已经大于0，无需继续
            }
            if (nums[i] + nums[nums.length-1] + nums[nums.length-2] < 0) {
                continue;  // 当前i与最大的两个数之和仍小于0，需要增大i
            }

            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int s = nums[i] + nums[j] + nums[k];
                if (s == 0) {
                    list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    // 跳过重复的j
                    while (j < k && nums[j] == nums[j+1]) j++;
                    // 跳过重复的k
                    while (j < k && nums[k] == nums[k-1]) k--;
                    j++;
                    k--;
                } else if (s > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return list;
    }
}

3.统计和小于目标的下标对数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeetCode8Test {
    @Test
    public void test(){
        List<Integer> nums = new ArrayList<>(Arrays.asList(-6,2,5,-2,-7,-1,3));
        int target = -2;
        System.out.println(countPairs(nums,target));
    }
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int count = 0;
        int i = 0;
        int j =nums.size()-1;
        while (i < j) {
            int sum = nums.get(i)+nums.get(j);
            if (sum < target) {
                count += j - i;
                i++;
            } else {
                j--;
            }
        }
        return count;
    }
}

4.最接近的三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class LeetCode9Test {
    @Test
    public void test(){
        int[] nums = {-1,2,1,-4};
        int target = 1;
        System.out.println(threeSumClosest(nums,target));
    }
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = nums[0]+nums[1]+nums[2];
        for (int i = 0; i < nums.length-2; i++) {
            int j = i + 1;
            int k = nums.length-1;
            while (j<k){
                int sum = nums[i]+nums[j]+nums[k];
                if (sum == target){
                    return target;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
                if (Math.abs(sum-target) < Math.abs(result-target)){
                    result = sum;
                }
            }
        }
        return result;
    }
}

5.四数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode10Test {
    @Test
    public void test(){
        int[] nums = {1,0,-1,0,-2,2};
        int target =0;
        System.out.println(fourSum(nums,target));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int a = 0; a < n - 3; a++) {
            if (a > 0 && nums[a] == nums[a-1]){
                continue;
            }
            if ((long)nums[a] + nums[a+1] + nums[a+2] + nums[a+3] > target) break;
            if ((long)nums[a] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;

            for (int b = a + 1; b < n - 2; b++) {
                if (b > a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                if ((long)nums[a] + nums[b] + nums[b+1] + nums[b+2] > target) break;
                if ((long)nums[a] + nums[b] + nums[n-2] + nums[n-1] < target) continue;

                int c = b + 1;
                int d = n - 1;
                while (c < d) {
                    int sum = nums[a]+nums[b]+nums[c]+nums[d];
                    if (sum == target){
                        result.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                        while (c < d && nums[c] == nums[c + 1]) c++;
                        while (c < d && nums[d] == nums[d - 1]) d--;
                        c++;
                        d--;
                    } else if (sum > target) {
                        d--;
                    } else {
                        c++;
                    }
                }
            }
        }
        return result;
    }
}

6.有效三角形的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package com.nianxi;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class LeetCode11Test {
    @Test
    public void test(){
        int[] nums = {2,2,3,4};
        System.out.println(triangleNumber(nums));
    }

    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int c = nums.length - 1; c > 1; c--) {
            if (nums[0]+nums[1]> nums[c]){
                count += (c + 1) * c * (c - 1) / 6;
                break;
            }
            if (nums[c-2]+nums[c-1]<=nums[c]){
                continue;
            }
            int a = 0;
            int b = c - 1;
            while (a < b) {
                if (nums[a]+nums[b]>nums[c]){
                    count+=b-a;
                    b--;
                } else {
                    a++;
                }
            }
        }
        return count;
    }
}