最长连续序列 (longestConsecutive)

https://leetcode.cn/problems/longest-consecutive-sequence

---

解法思路

用 target 挨个 减去 nums 中的项，然后得出结果，如果结果 nums 中存在，则记录下标

JavaScript

Golang

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{
		0, 1, 1, 2,
	}

	results := longestConsecutive(nums)
	fmt.Println("results", results)

	results2 := longestConsecutive2(nums)
	fmt.Println("results2", results2)
}

// 暴力求解
/*
下一个减去上一个，结果为1则判定为有效
*/
func longestConsecutive(nums []int) int {
	// 去重
	hasMap := map[int]bool{}
	newArr := []int{}
	for _, v := range nums {
		if !hasMap[v] {
			hasMap[v] = true
			newArr = append(newArr, v)
		}
	}
	// 排序
	sort.Ints(newArr)

	// fmt.Println("newArr", newArr)

	lineArr := []int{}
	// result := [][]int{}

	max := 0

	if len(newArr) == 1 {
		return 1
	}

	for idx, item := range newArr {
		nextIdx := idx + 1
		if nextIdx > len(newArr)-1 {
			nextIdx = 0
		}
		now := item
		next := newArr[nextIdx]

		if next-now == 0 {
			continue
		}

		if next-now == 1 {
			lineArr = append(lineArr, item)
		} else {
			lineArr = append(lineArr, item)
			// result = append(result, lineArr)
			if len(lineArr) > max {
				max = len(lineArr)
			}
			lineArr = []int{}
		}

	}

	// fmt.Println("result", result)

	return max
}

// 利用哈希表
/*
将数组映射成哈希表
然后在哈希表中找-1的数字是否存在
*/
func longestConsecutive2(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}
	longestStreak := 0
	for num := range numSet {
		if !numSet[num-1] {
			currentNum := num
			currentStreak := 1
			for numSet[currentNum+1] {
				currentNum++
				currentStreak++
			}
			if longestStreak < currentStreak {
				longestStreak = currentStreak
			}
		}
	}
	return longestStreak
}

// 暴力求解
var longestConsecutive = function (nums) {
  //去重
  const hasMap = {};
  const newArr = [];
  for (const item of nums) {
    if (!hasMap[item]) {
      hasMap[item] = true;
      newArr.push(item);
    }
  }
  // 排序
  newArr.sort((a, b) => {
    return a - b;
  });

  let lineArr = [];
  let result = [];

  let max = 0;

  if (newArr.length == 1) {
    return 1;
  }

  for (let i = 0; i < newArr.length; i++) {
    let nextIdx = i + 1;
    if (nextIdx > newArr.length) {
      nextIdx = 0;
    }
    const now = newArr[i];
    const next = newArr[nextIdx];
    if (next - now == 0) {
      continue;
    }
    if (next - now == 1) {
      lineArr.push(now);
    } else {
      lineArr.push(now);
      result.push(lineArr);
      if (lineArr.length > max) {
        max = lineArr.length;
      }
      lineArr = [];
    }
  }

  console.log('result', result);

  return max;
};

// 代码执行块
(function () {
  const nums = [100, 4, 200, 1, 3, 2];
  const result = longestConsecutive(nums);
  console.log('result', result);
})();