主題
題目連結(jié)：
題目意譯：
給定一個(gè)數(shù)字字串陣列 nums 以及一個(gè)數(shù)字字串 target，回傳 (i, j)（其中 i ≠ j）數(shù)對(duì)的數(shù)量使得字串串接 nums[i] + nums[j] 等於 target。
限制：
2 ≦ nums.length ≦ 100
1 ≦ nums[i].length ≦ 100
2 ≦ target.length ≦ 100
nums[i] 和 target 由數(shù)字組成。
nums[i] 和 target 沒有前導(dǎo)零。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = ["777","7","77","77"], target = "7777"
輸出： 4
解釋： 合法配對(duì)為：
- (0, 1): "777" + "7"
- (1, 0): "7" + "777"
- (2, 3): "77" + "77"
- (3, 2): "77" + "77"
範(fàn)例 2：
輸入： nums = ["123","4","12","34"], target = "1234"
輸出： 2
解釋： 合法配對(duì)為：
- (0, 1): "123" + "4"
- (2, 3): "12" + "34"
範(fàn)例 3：
輸入： nums = ["1","1","1"], target = "11"
輸出： 6
解釋： 合法配對(duì)為：
- (0, 1): "1" + "1"
- (1, 0): "1" + "1"
- (0, 2): "1" + "1"
- (2, 0): "1" + "1"
- (1, 2): "1" + "1"
- (2, 1): "1" + "1"
解題思維：
直接窮舉所有配對(duì)並判斷哪些合法當(dāng)然可行。
不過我們可以做得更好：
先利用雜湊表統(tǒng)計(jì)每一種數(shù)字字串的出現(xiàn)頻率。令 H[s] 為數(shù)字字串 s 在 nums 中的出現(xiàn)次數(shù)。
統(tǒng)計(jì)完後我們掃過一次每一種數(shù)字字串 s，如果 s 恰好為 target 的前綴，則：
判斷 s + s 是不是等於 target，如果是則把所求配對(duì)數(shù)加上 H[s] × (H[s] - 1)（因?yàn)槲覀兛梢栽?H[s] 個(gè)字串 s 中挑兩個(gè)出來）；
反之，則所求配對(duì)數(shù)將加上 H[s] × H[target - s]。其中 target - s 代表著 target 移除掉 s 這個(gè)前綴後剩餘的子字串。
每種數(shù)字字串掃完後並加總每種的貢獻(xiàn)配對(duì)數(shù)即是所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
