Map<Integer, Integer> map = new HashMap<>();<\/em><\/p>\n\n\n\n\u6bcf\u5b9a\u4e49\u4e00\u4e2a\u53d8\u91cf\u90fd\u8981\u82b1\u65f6\u95f4\u81f3\u5c11\u7a0d\u5fae\u60f3\u4e00\u4e2a\u53d8\u91cf\u547d\u540d\uff0c\u8fd9\u662f\u4e00\u4e2a\u6700\u57fa\u672c\u7684\u4e60\u60ef\u3002\u5199\u51fa\u7528map\u4f5c\u4e3a\u53d8\u91cf\u540d\u7684\u4eba\u7edd\u5bf9\u4e0d\u662f\u6709\u7ecf\u9a8c\u7684\u597d\u5de5\u7a0b\u5e08\u5e94\u8be5\u505a\u7684\u4e8b\u60c5\u3002<\/p>\n\n\n\n
\u597d\u4e86\uff0c\u8a00\u5f52\u6b63\u4f20\u3002<\/p>\n\n\n\n
Two Sum\u53ef\u4ee5\u7b97\u662f\u7b97\u6cd5\u9898\u91cc\u9762\u6700\u7b80\u5355\u7684\u4e4b\u4e00\u4e86\u3002\u4e0b\u9762\u662f\u9898\u76ee\u548cLeetCode Premium\u7ed9\u51fa\u7684\u4e00\u4e2aSolutionO(N) Solution.<\/p>\n\n\n\n
\u9898\u76ee:
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.
<\/p>\n\n\n\n
\u4e0b\u9762\u662f\u91c7\u7528Two Pass\u7684 O(N)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u89e3\u7b54:<\/p>\n\n\n\n
To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.
We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully.<\/p>\n\n\n\n
<\/p>\n\n\n\n
class Solution
{<\/em>
public int[] twoSum(int[] nums, int target)
{
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) { <\/em>
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target – nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
\/\/ In case there is no solution, we’ll just return null
return null;
}
}<\/em><\/p>\n\n\n\n
LeetCode\u91cc\u9762\u6ca1\u6709\u8bf4\u7684\u662f\u7b2c\u4e00\u4e2aloop\u53ef\u80fd\u5b58\u5728\u4e24\u4e2a\u672a\u77e5\u7684\u6570\u5b57\u76f8\u540c\u7684\u60c5\u51b5\u3002\u8fd9\u6837loop\u7ed3\u675f\u4ee5\u540emap\u91cc\u9762\u7684value\u5c31\u662f\u6700\u540e\u51fa\u73b0\u90a3\u4e2a\u6570\u5b57\u7684\u4f4d\u7f6e\u3002\u6bd4\u5982\u8bf4[1,2,3,2]\uff0cmap\u91cc\u9762\u662f[2,3] \u800c\u4e0d\u662f[2,1]\u3002 \u4f46\u662f\u8fd9\u4e2a\u89e3\u7b54\u4f9d\u7136\u662f\u5bf9\u7684\u662f\u56e0\u4e3a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u4e00\u5b9a\u662f\u4ece\u5c0f\u5230\u5927\u5faa\u73af\u7684\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u51fa\u73b0\u91cd\u590d\u4f7f\u7528\u540c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u6570\u5b57\u7684\u60c5\u51b5\u3002\u4f46\u662f\u5982\u679c\u628a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u5012\u5e8f\u7684\u8bdd\uff0c\u7b97\u6cd5\u5c31\u9519\u4e86\u3002
\u53ef\u80fd\u6709\u4eba\u4f1a\u95ee\u5982\u679c\u662f\u30101\uff0c2\uff0c2\uff0c2\uff0c3\u3011\uff0c\u540c\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u4e09\u4e2a\u600e\u4e48\u529e\uff1f\u5176\u5b9e\u9898\u76ee\u662f\u8981\u6c42\u662f\u53ef\u4ee5\u5047\u5b9a\u7ed3\u679c\u53ea\u6709\u552f\u4e00\u89e3\uff0c\u5982\u679c\u6709\u4e09\u4e2a\u7684\u8bdd\u5c31\u53ef\u80fd\u4f1a\u6709\u591a\u4e2a\u89e3\u4e86\u3002\u7b97\u6cd5\u7ec8\u5f52\u662f\u7b97\u6cd5\uff0ctwo sum\u7684\u9898\u76ee\u672c\u8eab\u7b80\u5316\u4e86\u5f88\u591a\u4e1c\u897f\uff0c\u6240\u4ee5\u8fd9\u79cdhash\u7684\u7b97\u6cd5\u5728\u771f\u5b9e\u573a\u666f\u4e2d\uff0c\u6ca1\u6709\u90a3\u4e9b\u9650\u5b9a\u6761\u4ef6\u7684\u8bdd\uff0c\u8fd8\u662f\u4f1a\u6709bug\u7684\u3002<\/p>\n\n\n\n
\u987a\u4fbf\u9644\u4e0aOne Pass\u5427\u3002One Pass\u5176\u5b9e\u6ca1\u5565\u533a\u522b\uff0c\u53cd\u5012\u4e0d\u5982two pass\u76f4\u89c2\u3002
<\/p>\n\n\n\n
class Solution
{
public int[] twoSum(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target – nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
\/\/ In case there is no solution, we’ll just return null
return null;
}
}<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6700\u5f00\u59cb\u5176\u5b9e\u60f3\u8bf4\u4e00\u4e0bLeedcode\u63d0\u4f9b\u7684\u5b9e\u73b0\u7684\u4ee3\u7801\u8d28\u91cf\u5176\u5b9e\u771f\u7684\u4e00\u822c\uff0c\u5982\u679c\u6709\u4eba\u9762\u8bd5\u7684\u65f6\u5019\u7528\u5b9e\u4f8b\u4ee3\u7801\u7684\u98ce\u683c\uff0c\u6211\u4f30\u8ba1\u7b97\u6cd5\u5199\u7684\u518d\u597d\u4e5f\u6ca1\u592a\u5927\u7528\u3002\u6700\u7b80\u5355\u7684\u53d8\u91cf\u547d\u540d\u3002\u5c3d\u7136\u6709\u8fd9\u6837\u7684\u4ee3\u7801: Map<Integer, Integer> map = new HashMap<>(); \u6bcf\u5b9a\u4e49\u4e00\u4e2a\u53d8\u91cf\u90fd\u8981\u82b1\u65f6\u95f4\u81f3\u5c11\u7a0d\u5fae\u60f3\u4e00\u4e2a\u53d8\u91cf\u547d\u540d\uff0c\u8fd9\u662f\u4e00\u4e2a\u6700\u57fa\u672c\u7684\u4e60\u60ef\u3002\u5199\u51fa\u7528map\u4f5c\u4e3a\u53d8\u91cf\u540d\u7684\u4eba\u7edd\u5bf9\u4e0d\u662f\u6709\u7ecf\u9a8c\u7684\u597d\u5de5\u7a0b\u5e08\u5e94\u8be5\u505a\u7684\u4e8b\u60c5\u3002 \u597d\u4e86\uff0c\u8a00\u5f52\u6b63\u4f20\u3002 Two Sum\u53ef\u4ee5\u7b97\u662f\u7b97\u6cd5\u9898\u91cc\u9762\u6700\u7b80\u5355\u7684\u4e4b\u4e00\u4e86\u3002\u4e0b\u9762\u662f\u9898\u76ee\u548cLeetCode Premium\u7ed9\u51fa\u7684\u4e00\u4e2aSolutionO(N) Solution. \u9898\u76ee:Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order. \u4e0b\u9762\u662f\u91c7\u7528Two Pass\u7684 O(N)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u89e3\u7b54: To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully. class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } \/\/ In case there is no solution, we’ll just return null return null; }} LeetCode\u91cc\u9762\u6ca1\u6709\u8bf4\u7684\u662f\u7b2c\u4e00\u4e2aloop\u53ef\u80fd\u5b58\u5728\u4e24\u4e2a\u672a\u77e5\u7684\u6570\u5b57\u76f8\u540c\u7684\u60c5\u51b5\u3002\u8fd9\u6837loop\u7ed3\u675f\u4ee5\u540emap\u91cc\u9762\u7684value\u5c31\u662f\u6700\u540e\u51fa\u73b0\u90a3\u4e2a\u6570\u5b57\u7684\u4f4d\u7f6e\u3002\u6bd4\u5982\u8bf4[1,2,3,2]\uff0cmap\u91cc\u9762\u662f[2,3] \u800c\u4e0d\u662f[2,1]\u3002 \u4f46\u662f\u8fd9\u4e2a\u89e3\u7b54\u4f9d\u7136\u662f\u5bf9\u7684\u662f\u56e0\u4e3a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u4e00\u5b9a\u662f\u4ece\u5c0f\u5230\u5927\u5faa\u73af\u7684\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u51fa\u73b0\u91cd\u590d\u4f7f\u7528\u540c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u6570\u5b57\u7684\u60c5\u51b5\u3002\u4f46\u662f\u5982\u679c\u628a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u5012\u5e8f\u7684\u8bdd\uff0c\u7b97\u6cd5\u5c31\u9519\u4e86\u3002\u53ef\u80fd\u6709\u4eba\u4f1a\u95ee\u5982\u679c\u662f\u30101\uff0c2\uff0c2\uff0c2\uff0c3\u3011\uff0c\u540c\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u4e09\u4e2a\u600e\u4e48\u529e\uff1f\u5176\u5b9e\u9898\u76ee\u662f\u8981\u6c42\u662f\u53ef\u4ee5\u5047\u5b9a\u7ed3\u679c\u53ea\u6709\u552f\u4e00\u89e3\uff0c\u5982\u679c\u6709\u4e09\u4e2a\u7684\u8bdd\u5c31\u53ef\u80fd\u4f1a\u6709\u591a\u4e2a\u89e3\u4e86\u3002\u7b97\u6cd5\u7ec8\u5f52\u662f\u7b97\u6cd5\uff0ctwo sum\u7684\u9898\u76ee\u672c\u8eab\u7b80\u5316\u4e86\u5f88\u591a\u4e1c\u897f\uff0c\u6240\u4ee5\u8fd9\u79cdhash\u7684\u7b97\u6cd5\u5728\u771f\u5b9e\u573a\u666f\u4e2d\uff0c\u6ca1\u6709\u90a3\u4e9b\u9650\u5b9a\u6761\u4ef6\u7684\u8bdd\uff0c\u8fd8\u662f\u4f1a\u6709bug\u7684\u3002 \u987a\u4fbf\u9644\u4e0aOne Pass\u5427\u3002One Pass\u5176\u5b9e\u6ca1\u5565\u533a\u522b\uff0c\u53cd\u5012\u4e0d\u5982two pass\u76f4\u89c2\u3002 class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } \/\/ In case there is no solution, we’ll just return null return null; }}<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,17],"tags":[],"class_list":["post-47","post","type-post","status-publish","format-standard","hentry","category-16","category-17"],"yoast_head":"\n
Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/liangqi.org\/?p=47\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey\" \/>\n<meta property=\"og:description\" content=\"\u6700\u5f00\u59cb\u5176\u5b9e\u60f3\u8bf4\u4e00\u4e0bLeedcode\u63d0\u4f9b\u7684\u5b9e\u73b0\u7684\u4ee3\u7801\u8d28\u91cf\u5176\u5b9e\u771f\u7684\u4e00\u822c\uff0c\u5982\u679c\u6709\u4eba\u9762\u8bd5\u7684\u65f6\u5019\u7528\u5b9e\u4f8b\u4ee3\u7801\u7684\u98ce\u683c\uff0c\u6211\u4f30\u8ba1\u7b97\u6cd5\u5199\u7684\u518d\u597d\u4e5f\u6ca1\u592a\u5927\u7528\u3002\u6700\u7b80\u5355\u7684\u53d8\u91cf\u547d\u540d\u3002\u5c3d\u7136\u6709\u8fd9\u6837\u7684\u4ee3\u7801: Map<Integer, Integer> map = new HashMap<>(); \u6bcf\u5b9a\u4e49\u4e00\u4e2a\u53d8\u91cf\u90fd\u8981\u82b1\u65f6\u95f4\u81f3\u5c11\u7a0d\u5fae\u60f3\u4e00\u4e2a\u53d8\u91cf\u547d\u540d\uff0c\u8fd9\u662f\u4e00\u4e2a\u6700\u57fa\u672c\u7684\u4e60\u60ef\u3002\u5199\u51fa\u7528map\u4f5c\u4e3a\u53d8\u91cf\u540d\u7684\u4eba\u7edd\u5bf9\u4e0d\u662f\u6709\u7ecf\u9a8c\u7684\u597d\u5de5\u7a0b\u5e08\u5e94\u8be5\u505a\u7684\u4e8b\u60c5\u3002 \u597d\u4e86\uff0c\u8a00\u5f52\u6b63\u4f20\u3002 Two Sum\u53ef\u4ee5\u7b97\u662f\u7b97\u6cd5\u9898\u91cc\u9762\u6700\u7b80\u5355\u7684\u4e4b\u4e00\u4e86\u3002\u4e0b\u9762\u662f\u9898\u76ee\u548cLeetCode Premium\u7ed9\u51fa\u7684\u4e00\u4e2aSolutionO(N) Solution. \u9898\u76ee:Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order. \u4e0b\u9762\u662f\u91c7\u7528Two Pass\u7684 O(N)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u89e3\u7b54: To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully. class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } \/\/ In case there is no solution, we’ll just return null return null; }} LeetCode\u91cc\u9762\u6ca1\u6709\u8bf4\u7684\u662f\u7b2c\u4e00\u4e2aloop\u53ef\u80fd\u5b58\u5728\u4e24\u4e2a\u672a\u77e5\u7684\u6570\u5b57\u76f8\u540c\u7684\u60c5\u51b5\u3002\u8fd9\u6837loop\u7ed3\u675f\u4ee5\u540emap\u91cc\u9762\u7684value\u5c31\u662f\u6700\u540e\u51fa\u73b0\u90a3\u4e2a\u6570\u5b57\u7684\u4f4d\u7f6e\u3002\u6bd4\u5982\u8bf4[1,2,3,2]\uff0cmap\u91cc\u9762\u662f[2,3] \u800c\u4e0d\u662f[2,1]\u3002 \u4f46\u662f\u8fd9\u4e2a\u89e3\u7b54\u4f9d\u7136\u662f\u5bf9\u7684\u662f\u56e0\u4e3a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u4e00\u5b9a\u662f\u4ece\u5c0f\u5230\u5927\u5faa\u73af\u7684\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u51fa\u73b0\u91cd\u590d\u4f7f\u7528\u540c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u6570\u5b57\u7684\u60c5\u51b5\u3002\u4f46\u662f\u5982\u679c\u628a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u5012\u5e8f\u7684\u8bdd\uff0c\u7b97\u6cd5\u5c31\u9519\u4e86\u3002\u53ef\u80fd\u6709\u4eba\u4f1a\u95ee\u5982\u679c\u662f\u30101\uff0c2\uff0c2\uff0c2\uff0c3\u3011\uff0c\u540c\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u4e09\u4e2a\u600e\u4e48\u529e\uff1f\u5176\u5b9e\u9898\u76ee\u662f\u8981\u6c42\u662f\u53ef\u4ee5\u5047\u5b9a\u7ed3\u679c\u53ea\u6709\u552f\u4e00\u89e3\uff0c\u5982\u679c\u6709\u4e09\u4e2a\u7684\u8bdd\u5c31\u53ef\u80fd\u4f1a\u6709\u591a\u4e2a\u89e3\u4e86\u3002\u7b97\u6cd5\u7ec8\u5f52\u662f\u7b97\u6cd5\uff0ctwo sum\u7684\u9898\u76ee\u672c\u8eab\u7b80\u5316\u4e86\u5f88\u591a\u4e1c\u897f\uff0c\u6240\u4ee5\u8fd9\u79cdhash\u7684\u7b97\u6cd5\u5728\u771f\u5b9e\u573a\u666f\u4e2d\uff0c\u6ca1\u6709\u90a3\u4e9b\u9650\u5b9a\u6761\u4ef6\u7684\u8bdd\uff0c\u8fd8\u662f\u4f1a\u6709bug\u7684\u3002 \u987a\u4fbf\u9644\u4e0aOne Pass\u5427\u3002One Pass\u5176\u5b9e\u6ca1\u5565\u533a\u522b\uff0c\u53cd\u5012\u4e0d\u5982two pass\u76f4\u89c2\u3002 class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } \/\/ In case there is no solution, we’ll just return null return null; }}\" \/>\n<meta property=\"og:url\" content=\"https:\/\/liangqi.org\/?p=47\" \/>\n<meta property=\"og:site_name\" content=\"Liangqi\u2018s Technical Journey\" \/>\n<meta property=\"article:published_time\" content=\"2022-01-27T23:20:28+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-01-27T23:49:36+00:00\" \/>\n<meta name=\"author\" content=\"liangqi\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"liangqi\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/liangqi.org\/?p=47#article\",\"isPartOf\":{\"@id\":\"https:\/\/liangqi.org\/?p=47\"},\"author\":{\"name\":\"liangqi\",\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"headline\":\"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684)\",\"datePublished\":\"2022-01-27T23:20:28+00:00\",\"dateModified\":\"2022-01-27T23:49:36+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/liangqi.org\/?p=47\"},\"wordCount\":413,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"articleSection\":[\"\u6280\u672f\",\"\u7b97\u6cd5\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/liangqi.org\/?p=47#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/liangqi.org\/?p=47\",\"url\":\"https:\/\/liangqi.org\/?p=47\",\"name\":\"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey\",\"isPartOf\":{\"@id\":\"https:\/\/liangqi.org\/#website\"},\"datePublished\":\"2022-01-27T23:20:28+00:00\",\"dateModified\":\"2022-01-27T23:49:36+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/liangqi.org\/?p=47#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/liangqi.org\/?p=47\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/liangqi.org\/?p=47#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/liangqi.org\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/liangqi.org\/#website\",\"url\":\"https:\/\/liangqi.org\/\",\"name\":\"Liangqi\u2018s Technical Journey\",\"description\":\"Chasing Excellence; Enjoy life.\",\"publisher\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/liangqi.org\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\",\"name\":\"liangqi\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg\",\"contentUrl\":\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg\",\"width\":2560,\"height\":1920,\"caption\":\"liangqi\"},\"logo\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/image\/\"},\"sameAs\":[\"https:\/\/liangqi.org\"],\"url\":\"https:\/\/liangqi.org\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/liangqi.org\/?p=47","og_locale":"en_US","og_type":"article","og_title":"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey","og_description":"\u6700\u5f00\u59cb\u5176\u5b9e\u60f3\u8bf4\u4e00\u4e0bLeedcode\u63d0\u4f9b\u7684\u5b9e\u73b0\u7684\u4ee3\u7801\u8d28\u91cf\u5176\u5b9e\u771f\u7684\u4e00\u822c\uff0c\u5982\u679c\u6709\u4eba\u9762\u8bd5\u7684\u65f6\u5019\u7528\u5b9e\u4f8b\u4ee3\u7801\u7684\u98ce\u683c\uff0c\u6211\u4f30\u8ba1\u7b97\u6cd5\u5199\u7684\u518d\u597d\u4e5f\u6ca1\u592a\u5927\u7528\u3002\u6700\u7b80\u5355\u7684\u53d8\u91cf\u547d\u540d\u3002\u5c3d\u7136\u6709\u8fd9\u6837\u7684\u4ee3\u7801: Map<Integer, Integer> map = new HashMap<>(); \u6bcf\u5b9a\u4e49\u4e00\u4e2a\u53d8\u91cf\u90fd\u8981\u82b1\u65f6\u95f4\u81f3\u5c11\u7a0d\u5fae\u60f3\u4e00\u4e2a\u53d8\u91cf\u547d\u540d\uff0c\u8fd9\u662f\u4e00\u4e2a\u6700\u57fa\u672c\u7684\u4e60\u60ef\u3002\u5199\u51fa\u7528map\u4f5c\u4e3a\u53d8\u91cf\u540d\u7684\u4eba\u7edd\u5bf9\u4e0d\u662f\u6709\u7ecf\u9a8c\u7684\u597d\u5de5\u7a0b\u5e08\u5e94\u8be5\u505a\u7684\u4e8b\u60c5\u3002 \u597d\u4e86\uff0c\u8a00\u5f52\u6b63\u4f20\u3002 Two Sum\u53ef\u4ee5\u7b97\u662f\u7b97\u6cd5\u9898\u91cc\u9762\u6700\u7b80\u5355\u7684\u4e4b\u4e00\u4e86\u3002\u4e0b\u9762\u662f\u9898\u76ee\u548cLeetCode Premium\u7ed9\u51fa\u7684\u4e00\u4e2aSolutionO(N) Solution. \u9898\u76ee:Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order. \u4e0b\u9762\u662f\u91c7\u7528Two Pass\u7684 O(N)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u89e3\u7b54: To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.We can reduce the lookup time from O(n) to O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say “near” because if a collision occurred, a lookup could degenerate to O(n) time. However, lookup in a hash table should be amortized O(1) time as long as the hash function was chosen carefully. class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } \/\/ In case there is no solution, we’ll just return null return null; }} LeetCode\u91cc\u9762\u6ca1\u6709\u8bf4\u7684\u662f\u7b2c\u4e00\u4e2aloop\u53ef\u80fd\u5b58\u5728\u4e24\u4e2a\u672a\u77e5\u7684\u6570\u5b57\u76f8\u540c\u7684\u60c5\u51b5\u3002\u8fd9\u6837loop\u7ed3\u675f\u4ee5\u540emap\u91cc\u9762\u7684value\u5c31\u662f\u6700\u540e\u51fa\u73b0\u90a3\u4e2a\u6570\u5b57\u7684\u4f4d\u7f6e\u3002\u6bd4\u5982\u8bf4[1,2,3,2]\uff0cmap\u91cc\u9762\u662f[2,3] \u800c\u4e0d\u662f[2,1]\u3002 \u4f46\u662f\u8fd9\u4e2a\u89e3\u7b54\u4f9d\u7136\u662f\u5bf9\u7684\u662f\u56e0\u4e3a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u4e00\u5b9a\u662f\u4ece\u5c0f\u5230\u5927\u5faa\u73af\u7684\uff0c\u8fd9\u6837\u5c31\u4e0d\u4f1a\u51fa\u73b0\u91cd\u590d\u4f7f\u7528\u540c\u4e00\u4e2a\u4f4d\u7f6e\u7684\u6570\u5b57\u7684\u60c5\u51b5\u3002\u4f46\u662f\u5982\u679c\u628a\u7b2c\u4e8c\u4e2a\u5faa\u73af\u5012\u5e8f\u7684\u8bdd\uff0c\u7b97\u6cd5\u5c31\u9519\u4e86\u3002\u53ef\u80fd\u6709\u4eba\u4f1a\u95ee\u5982\u679c\u662f\u30101\uff0c2\uff0c2\uff0c2\uff0c3\u3011\uff0c\u540c\u4e00\u4e2a\u6570\u5b57\u51fa\u73b0\u4e09\u4e2a\u600e\u4e48\u529e\uff1f\u5176\u5b9e\u9898\u76ee\u662f\u8981\u6c42\u662f\u53ef\u4ee5\u5047\u5b9a\u7ed3\u679c\u53ea\u6709\u552f\u4e00\u89e3\uff0c\u5982\u679c\u6709\u4e09\u4e2a\u7684\u8bdd\u5c31\u53ef\u80fd\u4f1a\u6709\u591a\u4e2a\u89e3\u4e86\u3002\u7b97\u6cd5\u7ec8\u5f52\u662f\u7b97\u6cd5\uff0ctwo sum\u7684\u9898\u76ee\u672c\u8eab\u7b80\u5316\u4e86\u5f88\u591a\u4e1c\u897f\uff0c\u6240\u4ee5\u8fd9\u79cdhash\u7684\u7b97\u6cd5\u5728\u771f\u5b9e\u573a\u666f\u4e2d\uff0c\u6ca1\u6709\u90a3\u4e9b\u9650\u5b9a\u6761\u4ef6\u7684\u8bdd\uff0c\u8fd8\u662f\u4f1a\u6709bug\u7684\u3002 \u987a\u4fbf\u9644\u4e0aOne Pass\u5427\u3002One Pass\u5176\u5b9e\u6ca1\u5565\u533a\u522b\uff0c\u53cd\u5012\u4e0d\u5982two pass\u76f4\u89c2\u3002 class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target – nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } \/\/ In case there is no solution, we’ll just return null return null; }}","og_url":"https:\/\/liangqi.org\/?p=47","og_site_name":"Liangqi\u2018s Technical Journey","article_published_time":"2022-01-27T23:20:28+00:00","article_modified_time":"2022-01-27T23:49:36+00:00","author":"liangqi","twitter_card":"summary_large_image","twitter_misc":{"Written by":"liangqi","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/liangqi.org\/?p=47#article","isPartOf":{"@id":"https:\/\/liangqi.org\/?p=47"},"author":{"name":"liangqi","@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"headline":"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684)","datePublished":"2022-01-27T23:20:28+00:00","dateModified":"2022-01-27T23:49:36+00:00","mainEntityOfPage":{"@id":"https:\/\/liangqi.org\/?p=47"},"wordCount":413,"commentCount":0,"publisher":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"articleSection":["\u6280\u672f","\u7b97\u6cd5"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/liangqi.org\/?p=47#respond"]}]},{"@type":"WebPage","@id":"https:\/\/liangqi.org\/?p=47","url":"https:\/\/liangqi.org\/?p=47","name":"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684) - Liangqi\u2018s Technical Journey","isPartOf":{"@id":"https:\/\/liangqi.org\/#website"},"datePublished":"2022-01-27T23:20:28+00:00","dateModified":"2022-01-27T23:49:36+00:00","breadcrumb":{"@id":"https:\/\/liangqi.org\/?p=47#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/liangqi.org\/?p=47"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/liangqi.org\/?p=47#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/liangqi.org\/"},{"@type":"ListItem","position":2,"name":"Two Sum\u7b97\u6cd5\u7684\u5c0ftrick\uff08Leetcode\u7684premium\u7684\u89e3\u7b54\u6ca1\u6709\u8bb2\u5230\u7684)"}]},{"@type":"WebSite","@id":"https:\/\/liangqi.org\/#website","url":"https:\/\/liangqi.org\/","name":"Liangqi\u2018s Technical Journey","description":"Chasing Excellence; Enjoy life.","publisher":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/liangqi.org\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3","name":"liangqi","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/liangqi.org\/#\/schema\/person\/image\/","url":"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg","contentUrl":"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg","width":2560,"height":1920,"caption":"liangqi"},"logo":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/image\/"},"sameAs":["https:\/\/liangqi.org"],"url":"https:\/\/liangqi.org\/?author=1"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=47"}],"version-history":[{"count":4,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/47\/revisions"}],"predecessor-version":[{"id":54,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/47\/revisions\/54"}],"wp:attachment":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}