LeetCode 1. Two Sum
给定一个整数数组,返回两个数字的索引,使得它们加起来等于一个特定的目标值。 您可以假设每个输入都有一且只有一个答案,数组中每个元素只能使用一次。 Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int[] nums = { 7, 11, 15 ,2}; int target = 9; var numarr = TwoSum(nums, target); } // right hash: time O(n) (degenerate when collison occured) ususlly O(1) (insert and search) space: O(n) result: 496ms public static int[] TwoSum(int[] nums, int target) {
int[] result = new int[2]; //[0,3],[3,0]
Dictionary<int, int> table = new Dictionary<int,int>(); // use empty constructor, result: 544 ms
for (int i = 0; i < nums.Length; i++)
{
int another = target - nums[i];
if (table.ContainsKey(another))
{
int anotherIndex = table[another];
result[0] = anotherIndex > i ? i : anotherIndex;
result[1] = anotherIndex < i ? i : anotherIndex;
return result;
}
else
{
if (!table.ContainsKey(nums[i]))
{
table.Add(nums[i], i);
}
}
}
throw new Exception("no answer");
} } }
相关文章
- Java实现 LeetCode第30场双周赛 (题号5177,5445,5446,5447)
- Java实现 LeetCode 753 破解保险箱(递归)
- Java实现 LeetCode 730 统计不同回文子字符串(动态规划)
- Java实现 LeetCode 258 各位相加
- Java实现 LeetCode 219 存在重复元素 II(二)
- Java实现 LeetCode 121 买卖股票的最佳时机
- Java实现 LeetCode 18 四数之和
- Java实现LeetCode #986 - Interval List Intersections
- LeetCode(3):无重复字符的最长子串
- [LeetCode] Two Sum
- LeetCode(68):文本左右对齐
- LeetCode-307. 区域和检索 - 数组可修改【分块处理,线段树,树状数组】
- leetcode 576. 出界的路径数
- 【LeetCode Weekly Contest 26 Q4】Split Array with Equal Sum
- 【LeetCode-面试算法经典-Java实现】【066-Plus One(加一)】
- Leetcode 2176. 统计数组中相等且可以被整除的数对
- Leetcode 1598. 文件夹操作日志搜集器
- [LeetCode] 40. Combination Sum II ☆☆☆(数组相加等于指定的数)
- [LeetCode] 39. Combination Sum ☆☆☆(数组相加等于指定的数)
- Leetcode--Two Sum
- leetcode 108. Convert Sorted Array to Binary Search Tree
- leetcode 226. Invert Binary Tree