{"id":2248,"date":"2018-03-20T20:33:59","date_gmt":"2018-03-21T03:33:59","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2248"},"modified":"2018-03-20T20:40:43","modified_gmt":"2018-03-21T03:40:43","slug":"leetcode-594-longest-harmonious-subsequence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-594-longest-harmonious-subsequence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 594. Longest Harmonious Subsequence"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/longest-harmonious-subsequence\/description\/\">https:\/\/leetcode.com\/problems\/longest-harmonious-subsequence\/description\/<\/a><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u627e\u4e00\u4e2a\u6700\u957f\u5b50\u5e8f\u5217\uff0c\u8981\u6c42\u5b50\u5e8f\u5217\u4e2d\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u7684\u5dee\u662f1\u3002<\/p>\n<p>We define a harmonious array is an array where the difference between its maximum value and its minimum value is\u00a0<b>exactly<\/b>\u00a01.<\/p>\n<p>Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Subsequence\">subsequences<\/a>.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> [1,3,2,2,5,2,3,7]\r\n<b>Output:<\/b> 5\r\n<b>Explanation:<\/b> The longest harmonious subsequence is [3,2,2,2,3].\r\n<\/pre>\n<p><b>Note:<\/b>\u00a0The length of the input array will not exceed 20,000.<\/p>\n<h1><strong>Solution1: HashTable<\/strong><\/h1>\n<p>Time complexity: O(n)<br \/>\nSpace complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 127 ms\r\nclass Solution {\r\npublic:\r\n  int findLHS(vector&lt;int&gt;&amp; nums) {\r\n    unordered_map&lt;int, int&gt; counts;\r\n    int ans = 0;\r\n    for (int num : nums) {\r\n      ++counts[num];      \r\n      int l = counts[num - 1];\r\n      int h = counts[num + 1];      \r\n      if (l || h)\r\n        ans = max(ans, counts[num] + max(l, h));\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<pre class=\"lang:default decode:true \">\/\/ Running time: 109 ms\r\nclass Solution {\r\npublic:\r\n  int findLHS(vector&lt;int&gt;&amp; nums) {\r\n    unordered_map&lt;int, int&gt; counts;\r\n    int ans = 0;\r\n    for (int num : nums) {\r\n      const int c = ++counts[num];\r\n      auto it1 = counts.find(num - 1);\r\n      auto it2 = counts.find(num + 1);\r\n      if (it1 != counts.end())\r\n        ans = max(ans, c + it1-&gt;second);\r\n      if (it2 != counts.end())\r\n        ans = max(ans, c + it2-&gt;second);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 102 ms\r\nclass Solution {\r\npublic:\r\n  int findLHS(vector&lt;int&gt;&amp; nums) {\r\n    unordered_map&lt;int, int&gt; counts;\r\n    int ans = 0;\r\n    for (int num : nums)\r\n      ++counts[num];\r\n    \r\n    for (const auto&amp; p : counts) {\r\n      auto it1 = counts.find(p.first - 1);\r\n      auto it2 = counts.find(p.first + 1);\r\n      if (it1 != counts.end())\r\n        ans = max(ans, p.second + it1-&gt;second);\r\n      if (it2 != counts.end())\r\n        ans = max(ans, p.second + it2-&gt;second);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem https:\/\/leetcode.com\/problems\/longest-harmonious-subsequence\/description\/ \u9898\u76ee\u5927\u610f\uff1a\u627e\u4e00\u4e2a\u6700\u957f\u5b50\u5e8f\u5217\uff0c\u8981\u6c42\u5b50\u5e8f\u5217\u4e2d\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u7684\u5dee\u662f1\u3002 We define a harmonious array is an array where the difference between its maximum value and its minimum value is\u00a0exactly\u00a01. Now, given&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,117,229],"class_list":["post-2248","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-longest","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2248","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2248"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2248\/revisions"}],"predecessor-version":[{"id":2254,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2248\/revisions\/2254"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}