{"id":4977,"date":"2019-03-16T23:37:40","date_gmt":"2019-03-17T06:37:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4977"},"modified":"2019-03-16T23:38:14","modified_gmt":"2019-03-17T06:38:14","slug":"leetcode-1013-pairs-of-songs-with-total-durations-divisible-by-60","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1013-pairs-of-songs-with-total-durations-divisible-by-60\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60"},"content":{"rendered":"\n<p>In a list of songs, the&nbsp;<code>i<\/code>-th&nbsp;song has a duration of&nbsp;<code>time[i]<\/code>&nbsp;seconds.&nbsp;<\/p>\n\n\n\n<p>Return the number of pairs of songs for which their total&nbsp;duration in seconds is divisible by&nbsp;<code>60<\/code>.&nbsp; Formally, we want the number of&nbsp;indices&nbsp;<code>i &lt; j<\/code>&nbsp;with&nbsp;<code>(time[i] + time[j]) % 60 == 0<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[30,20,150,100,40]\n<strong>Output: <\/strong>3\n<strong>Explanation: <\/strong>Three pairs have a total duration divisible by 60:\n(time[0] = 30, time[2] = 150): total duration 180\n(time[1] = 20, time[3] = 100): total duration 120\n(time[1] = 20, time[4] = 40): total duration 60\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[60,60,60]\n<strong>Output: <\/strong>3\n<strong>Explanation: <\/strong>All three pairs have a total duration of 120, which is divisible by 60.\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= time.length &lt;= 60000<\/code><\/li><li><code>1 &lt;= time[i] &lt;= 500<\/code><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Two Sum of 60<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(60)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 36 ms, 11.6 MB\nclass Solution {\npublic:\n  int numPairsDivisibleBy60(vector<int>& time) {\n    vector<int> c(60);\n    int ans = 0;    \n    for (int t : time) {\n      t %= 60;\n      ans += c[(60 - t) % 60];\n      ++c[t];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a list of songs, the&nbsp;i-th&nbsp;song has a duration of&nbsp;time[i]&nbsp;seconds.&nbsp; Return the number of pairs of songs for which their total&nbsp;duration in seconds is divisible&#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":[222,82,208],"class_list":["post-4977","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-easy","tag-hashtable","tag-two-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4977","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=4977"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4977\/revisions"}],"predecessor-version":[{"id":4980,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4977\/revisions\/4980"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}