每日一題

兩數(shù)之和

題目鏈接

思路

注：本題只采用暴力解法，時間復雜度為O(n²)，如果采用哈希表，可以將時間復雜度降到O(n)，但由于筆者還未對哈希表展開學習，故不做討論

• 我們直接用兩層for循環(huán)來解決問題

• 第一層for循環(huán)用來遍歷整個數(shù)組，第二層for循環(huán)用來判斷遍歷的兩個數(shù)的和是否等于target

  for(int i = 0; i < numsSize - 1; i++)
      {
          for(int j = i + 1; j < numsSize; j++)
          {
              if(nums[i] + nums[j] == target)
              {
                  ……………………;
              }
          }
      }
  

實現(xiàn)代碼

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    //確定返回數(shù)組的大小
    *returnSize = 2;
    //申請的返回數(shù)組
    int *res = (int *)malloc(sizeof(int) * 2);
    //尋找滿足條件的兩個數(shù)
    for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                res[0] = i;
                res[1] = j;
            }
        }
    }
    //返回這兩個數(shù)的下標
    return res;
}

拓展

• 這道題要求返回的是滿足條件的兩個數(shù)的下標，但如果將題目要求改為返回這兩個數(shù)的值呢？

思路

• 當然我們同樣可以上面的暴力解法來解決問題，但有沒有效率更高的方法呢？

• 我們可以采用雙指針的方法

• 首先我們假設題目給的數(shù)組是一個有序數(shù)組，那題解過程如圖所示：

  

• 由此可見，要使用雙指針的方法，就一定要確保數(shù)組是有序的（只有這樣，才能保證i右移后，nums[i] + nums[j]會變大，j左移后，nums[i] + nums[j]會變小），因此，我們最開始就要用排序算法來使數(shù)組nuns有序。文章來源地址http://www.zghlxwxcb.cn/news/detail-467337.html

實現(xiàn)代碼

void Sort(int *nums, int numsSize)
{
    for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] > nums[j])
            {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *res = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    //排序
    Sort(nums,numsSize);
    //從數(shù)組的頭和尾對數(shù)組進行遍歷
    int i = 0, j = numsSize - 1;
    //找到符合條件的兩個數(shù)
    while(i < j)
    {
        if(nums[i] + nums[j] > target)
            j--;
        else if(nums[i] + nums[j] < target)
            i++;
        else
        {
            res[0] = nums[i];
            res[1] = nums[j];
            break;
        }
    }
    //返回數(shù)組
    return res;
}

到了這里，關于每日一題——兩數(shù)之和（返回下標和返回數(shù)值兩種情況）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！