C#算法如何實現兩數之和

小編給大家分享一下C#算法如何實現兩數之和，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

題目

給定一個整數數組 nums和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，并返回他們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

提示：不能自身相加。

測試用例

[2,7,11,15]

9

預期結果

[0,1]

 格式模板

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
　　　　/*
　　　　代碼
　　　　*/
        }
    }

筆者的代碼，僅供參考

使用暴力方法，運行時間 700ms-1100ms

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
         int [] a = new int[2];
            for (int i = 0; i < nums.Length - 1; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] + nums[j] == target)
                    {
                        a[0] = i;
                        a[1] = j;
                    }
                }
            }
            return a;
        }
    }

運行時間 400ms-600ms

由于使用的是哈希表，所以缺點是鍵不能相同。

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
                     int[] a = new int[2];
            System.Collections.Hashtable hashtable = new System.Collections.Hashtable();
            for(int i = 0; i < nums.Length; i++)
            {
                hashtable.Add(nums[i], i);
            }
            for(int i = 0; i < nums.Length; i++)
            {
                int complement = target - nums[i];
                if (hashtable.ContainsKey(complement) && int.Parse(hashtable[complement].ToString())!=i)
                {
                    a[0] = i;
                    a[1] = int.Parse(hashtable[complement].ToString());
                }
            }
            return a;
        }
    }

還是哈希表，缺點是哈希表存儲的類型是object，獲取值時需要進行轉換。

        public int[] TwoSum(int[] nums, int target)
        {
            int[] a = new int[2];
            System.Collections.Hashtable h = new System.Collections.Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                int c = target - nums[i];
                if (h.ContainsKey(c))
                {
                    a[0] = int.Parse(h[c].ToString()) <= nums[i] ? int.Parse(h[c].ToString()) : i;
                    a[1] = int.Parse(h[c].ToString()) > nums[i] ? int.Parse(h[c].ToString()) : i;
                }
                else if (!h.ContainsKey(nums[i]))
                {
                    h.Add(nums[i], i);
                }
            }
            return a;
        }

抄一下別人的

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int[] res = {0, 0};
        int len = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for (int i = 0; i < len; i++)
        {
            int query = target - nums[i];
            if (dict.ContainsKey(query))
            {
                int min = (i <= dict[query]) ? i : dict[query];
                int max = (i <= dict[query]) ? dict[query] : i;
                return new int[] { min, max };
            }
            else if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], i);
            }
        }

        return res;
    }
}

以上是“C#算法如何實現兩數之和”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！