Java-LeetCode128. 最长连续序列-HashMap | 排序

• 算法
  • 1.HashMap保存每个连续序列中以左边界和右边界的值为key，序列长度为value的键值对
  • 2.每次遇到新的元素x，检查HashMap中是否存在x-1和x+1的序列以及序列长度left和right；计算x所在的序列长度，并更新x、x-left（序列的左边界）、x+right（序列的右边界）的value为这个长度
  • 3.循环的过程中持续更新max

public int longestConsecutive(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    int max = 0;
    for (int x : nums) {
        if (!map.containsKey(x)) {
            int left = map.getOrDefault(x - 1, 0);
            int right = map.getOrDefault(x + 1, 0);
            int sum = left + right + 1;
            map.put(x, sum);
            map.put(x - left, sum);
            map.put(x + right, sum);
            max = Math.max(max, sum);
        }
    }
    return max;
}

• 算法
  • 1.排序数组
  • 2.统计连续序列长度：遇到重复元素跳过；遇到不连续元素重置；遇到连续元素加一并更新max

public int longestConsecutive(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    Arrays.sort(nums);
    int max = 1;
    int continuousLength = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1] + 1) {
            continuousLength++;
            max = Math.max(max, continuousLength);
        } else if (nums[i] == nums[i-1]) {
            continue;
        } else {
            continuousLength = 1;
        }
    }
    return max;
}