莫轩然

字节跳动数组与排序挑战

2020/03/16 算法 数组，排序

字节跳动数组与排序挑战题集，从基础概念到实际问题。

无重复字符的最长子串

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。

示例1：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
思路

排序+双指针 详见代码注释

代码
方法 排序+双指针
package com.moxuanran.algorithm.array;

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

/**
 * @author 莫轩然
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] sums) {
        List<List<Integer>> res = new ArrayList<>();
        //边界条件校验
        if(sums == null || 3 > sums.length ){
            return res;
        }
        //数组排序
        Arrays.sort(sums);

        for (int i = 0; i < sums.length; i++) {
            int l = i + 1;
            int r = sums.length - 1;

            //由于排序过，若sums[i]大于0，则不可能后续和为0
            if (sums[i] > 0) {
                break;
            }
            //去除重复解
            if(i>0 && sums[i]==sums[i+1]){
                continue;
            }
            while (l < r) {
                int sum = sums[i] + sums[l] + sums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(sums[i], sums[l], sums[r]));
                    //去除重复解
                    while (l<r && sums[l]==sums[l+1]){l++;}
                    while (l<r && sums[r]==sums[r-1]){r--;}
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else{
                    r--;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        ThreeSum threeSum = new ThreeSum();
        int[] sums = new int[]{-1, -2, 1, 0, 2, 3};
        System.out.println( threeSum.threeSum(sums));
    }
}

Search

    Table of Contents