leetcode.哈希表.594最长和谐子序列-Java

1. 具体题目：

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]　　输出: 5　　原因: 最长的和谐数组是：[3,2,2,2,3]

说明: 输入的数组长度最大不超过20,000.

2. 思路分析：

由于题目不要求子序列中元素在原数组中是连续的，只要求该子序列中元素最多即可。所以考虑在遍历数组时记录各元素的个数，将其记录在一个哈希表中(key-num, value-num个数)。

而对于一个数"num"，可以与其组成和谐序列的数只有"num+1"或"num-1"，所以对于"num"，当前最长和谐序列的长度就是"num的个数" + "num+1的个数"，或者"num的个数" + "num-1的个数"，那么在遍历数组的同时就可以更新结果值longest。

注意：若对于"num"，当前map中没有"num+1"或"num-1"，那么其和谐序列长度为0。

3. 代码：

 public int findLHS(int[] nums) {

         HashMap<Integer,Integer> map = new HashMap<>();

         int longest = 0;

         for(int i = 0; i < nums.length; i++){

             if(map.containsKey(nums[i])){

                 int newValue = map.get(nums[i]) + 1;

                 map.put(nums[i], newValue);

             }else{

                 map.put(nums[i], 1);

             }

             int temp =

                 map.containsKey(nums[i] - 1) ? map.get(nums[i] - 1) + map.get(nums[i]) : 0;

             longest = Math.max(longest, temp);

             temp =

                 map.containsKey(nums[i] + 1) ? map.get(nums[i] + 1) + map.get(nums[i]) : 0;

             longest = Math.max(longest, temp);

         }

         return longest;

     }

4. 代码优化：

//冗余，可以用一个方法代替

for(int i = 0; i < nums.length; i++){

            if(map.containsKey(nums[i])){

                int newValue = map.get(nums[i]) + 1;

                map.put(nums[i], newValue);

}else{

                map.put(nums[i], 1);

}

//HashMap api中方法getOrDefault()

 map.put(num, map.getOrDefault(num, 0) + 1);

巴特西

leetcode.哈希表.594最长和谐子序列-Java

最新文章

热门文章