leetcode454_go_四數相加II

2020-09-14 每天都AC

題目

給定四個包含整數的數組列表 A , B , C , D ,計算有多少個元組 (i, j, k, l) ，

使得 A[i] + B[j] + C[k] + D[l] = 0。

為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 。

所有整數的範圍在 -228 到 228 - 1 之間，最終結果不會超過 231 - 1 。

例如:輸入:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

輸出:2

解釋:兩個元組如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解題思路分析

1、哈希輔助；時間複雜度O(n^2)，空間複雜度O(n^2)


func fourSumCount(A []int, B []int, C []int, D []int) int { res := 0 m := make(map[int]int) for _, a := range A { for _, b := range B { m[a+b]++ } } for _, c := range C { for _, d := range D { res = res + m[0-c-d] } } return res}

2、哈希輔助；時間複雜度O(n^2)，空間複雜度O(n^2)

func fourSumCount(A []int, B []int, C []int, D []int) int { res := 0 mA := make(map[int]int) mB := make(map[int]int) for _, a := range A { for _, b := range B { mA[a+b]++ } } for _, c := range C { for _, d := range D { mB[c+d]++ } } for k, v := range mA { res = res + v*mB[-k] } return res}

總結

Medium題目，幾數之和系列問題
leetcode 1.兩數之和
leetcode 167.兩數之和II-輸入有序數組
leetcode 653.兩數之和IV-輸入BST 樹 Easy 完成
leetcode 15.三數之和
leetcode 16.最接近的三數之和
leetcode 18.四數之和

相關焦點

  • leetcode之字符串相加
    序本文主要記錄一下leetcode之字符串相加提示：num1 和num2 的長度都小於 5100num1 和num2 都只包含數字 0-9num1 和num2 都不包含任何前導零你不能使用任何內建 BigInteger 庫， 也不能直接將輸入的字符串轉換為整數形式來源：力扣（LeetCode）連結：https://leetcode-cn.com
  • LeetCode 2. 兩數相加
    如果，我們將這兩個數相加起來，則會返回一個新的鍊表來表示它們的和。您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。考慮到進位:獲取鍊表上相同位數的元素並相加得到x如果之前上一個有進位標誌,則x++,設置進位標誌為false
  • 一文學會哈希法解題（leetcode哈希表面試高頻題目總結）
    題解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0349.兩個數組的交集.mdleetcode 202.快樂數題解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0001.兩數之和.mdleetcode 454.四數相加II
  • LeetCode筆記｜140：單詞拆分 II
    wordBreak.offerFirst(word); wordBreaks.add(wordBreak); } } } map.put(index, wordBreaks); } return map.get(index); }}作者：LeetCode-Solution連結：https://leetcode-cn.com
  • 雙指針法：一樣的道理，能解決四數之和
    滿足要求的四元組集合為：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]思路四數之和，和三數之和是一個思路，都是使用雙指針法, 基本解法就是在三數之和 的基礎上再套一層for循環。
  • 程式設計師面試題：Leetcode真題講解，兩數相加
    如果，我們將這兩個數相加起來，則會返回一個新的鍊表來表示它們的和。您可以假設除了數字0之外，這兩個數都不會以0開頭。一位數和一位數相加，大於10時候，除以10，商為進位數，餘數為該位的數。時間複雜度: o(n)使用Python來真正模擬過程，代碼很長，但是很好理解，用C++和Java來簡化過程。
  • 大廠經典筆試題—LeetCode 01兩數之和&02兩數相加
    因為如果從數的特性來看：數是一對形式出現的一對有前後位置之分，在遍歷到前的時候不一定會找到後面的元素，但是遍歷到後面的元素前面一定被我們存儲了。如果，我們將這兩個數相加起來，則會返回一個新的鍊表來表示它們的和。您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
  • leetcode673_go_最長遞增子序列的個數
    題目給定一個未排序的整數數組，找到最長遞增子序列的個數。示例 1:輸入: [1,3,5,4,7] 輸出: 2解釋: 有兩個最長遞增子序列，分別是 [1, 3, 4, 7] 和[1, 3, 5, 7]。n; i++ { if dp[i] == maxValue { res = res + count[i] } } return res}func max(a, b int) int { if a > b { return a } return b}總結Medium題目，題目意思同leetcode
  • 「Leetcode簡潔筆記」第18題：四數之和
    啊～～～四數 你還比三數多一數。本文答案參考自leetcode官方題解【方法1】不會吧，不會吧，不會還有人用四重for循環吧？[看]【方法2】排序 + 雙指針【時間複雜度 O(n^3) 空間複雜度 O(log n)】還是跟三數之和的解法相似，不過這次是在兩重循環中使用雙指針（當然得先排序）上圖：
  • leetcode518_go_零錢兌換II
    1; j <= amount; j++ { if j-coins[i-1] >= 0 { dp[j] = dp[j] + dp[j-coins[i-1]] } } } return dp[amount]}總結Medium題目，完全背包問題，零錢兌換系列題目leetcode
  • leetcode樹之從上到下列印二叉樹
    序本文主要記錄一下leetcode樹之上到下列印二叉樹例如:給定二叉樹: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其層次遍歷結果：[ [3], [9,20], [15,7]]提示： 節點總數 <= 1000注意：本題與主站 102 題相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
  • leetcode140_go_單詞拆分II
    arr { res = append(res, s[level:i]+&34;+str) } } else { res = append(res, s[level:i]) } } } visited[level] = res return res}總結Hard題目，本題是leetcode
  • Leetcode階段總結：第1~5題
    leetcode刷著刷著就索然無味了，那就先總結一下吧（[笑哭]）第1題：兩數之和這道題要我們在一串數字中找出相加等於某個數的兩個數。第2題：兩數相加這道題需要我們提取兩個鍊表中的數字，然後相加，再將這個和構造成另一個鍊表。要點1：我們可以在遍歷鍊表時 同時 將各個位數上的數相加（注意要進位）。
  • leetcode哈希表之好數對的數目
    序本文主要記錄一下leetcode哈希表之好數對的數目如果一組數字 (i,j) 滿足 nums[i] == nums[j] 且 i < j ，就可以認為這是一組 好數對 。返回好數對的數目。
  • leetcode-第1題-兩數之和
    // 示例:// 給定 nums = [2, 7, 11, 15], target = 9//因為 nums[0] + nums[1] = 2 + 7 = 9//所以返回 [0, 1]// Related Topics 數組 哈希表// 8674 0package com.zqh.leetcode.editor.cn;import java.util.Arrays;import java.util.HashMap
  • 劍指 Offer 56 - II. 數組中數字出現的次數 II
    , 沒有任何意義換個角度分析, 如果我們單獨統計每個數字二進位每一位上為 1 的次數並累加, 那麼對於出現 3 次的數而言, 它們的這一位為 1 的次數之和一定是 3 的倍數很顯然, 加上了單獨出現 1 次的數之後, 這一位上的次數除以 3 的餘數要麼是 0 (代表這個數字這一位是 0), 要麼是 1(代表這個數字這一位是 1),
  • leetcode117_go_填充節點下一個右側節點指針II
    提示： 樹中的節點數小於 6000 -100 <= node.val <= 100解題思路分析1、遞歸；時間複雜度O(n)，空間複雜度O(log(n))func connect(root *Node) *Node { if root
  • leetcode樹之從根到葉的二進位數之和
    序本文主要記錄一下leetcode樹之從根到葉的二進位數之和每一條從根到葉的路徑都代表一個從最高有效位開始的二進位數。例如，如果路徑為 0 -> 1 -> 1 -> 0 -> 1，那麼它表示二進位數 01101，也就是 13 。對樹上的每一片葉子，我們都要找出從根到該葉子的路徑所表示的數字。以 10^9 + 7 為模，返回這些數字之和。示例：!
  • leetcode樹之路徑總和
    序本文主要記錄一下leetcode樹之路徑總和>題目 給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等於目標和。 來源：力扣（LeetCode） 連結：https://leetcode-cn.com/problems/path-sum 著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。題解 /** * Definition for a binary tree node.