程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:4Sum

leetcode筆記:4Sum

編輯:關於C++

一、題目描述

這裡寫圖片描述

二、解題技巧

這道題從表面上看與3Sum極其相似,事實上確實可以使用相同的思維和方法,只不過這樣做的話,時間復雜度為O(n^3),空間復雜度為O(1)將超時。

這道題也可以在排序之後先計算後面兩個數的和,將其方法一個哈希表中,由於可能存在不同的兩個數的和為相同值,因此,可以考慮將和為相同的值放在一個鏈表中,然後將變量頭放在哈希表中。然後再按照3Sum的思路,不過第三個數在這裡變成了第三個和第四個數的和,通過哈希表可以方便地找到和為固定值的數的鏈表,就可以找到符合條件的四個數。這種方法的時間復雜度為O(n^2),空間復雜度也為O(n^2)。<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPsj9oaLKtcD9tPrC6zwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> class Solution { public: vector > fourSum(vector &num, int target) { vector > Result; int Size = num.size(); if (Size < 4) { return Result; } // sort the array sort(num.begin(), num.end()); for (int Index_first = 0; Index_first < (Size - 3); Index_first++) { int First = num[Index_first]; if ((Index_first != 0) && (num[Index_first - 1] == num[Index_first])) { continue; } for (int Index_second = Index_first + 1; Index_second < (Size - 2); Index_second++) { if ((Index_second != (Index_first + 1)) && (num[Index_second - 1] == num[Index_second])) { continue; } int Second = num[Index_second]; int Index_third = Index_second + 1; int Index_foud = Size - 1; while (Index_third < Index_foud) { int Third = num[Index_third]; int Fourd = num[Index_foud]; int Sum = First + Second + Third + Fourd; if (Sum == target) { vector Tmp; Tmp.push_back(First); Tmp.push_back(Second); Tmp.push_back(Third); Tmp.push_back(Fourd); Result.push_back(Tmp); Index_third++; while ((Index_third <= (Size - 1)) && (num[Index_third] == num[Index_third - 1])) { Index_third++; } Index_foud--; while ((Index_foud > Index_second) && (num[Index_foud] == num[Index_foud + 1])) { Index_foud--; } } if (Sum < target) { Index_third++; while ((Index_third < Size) && (num[Index_third] == num[Index_third - 1])) { Index_third++; } } if (Sum > target) { Index_foud--; while ((Index_foud > Index_second) && (num[Index_foud] == num[Index_foud + 1])) { Index_foud--; } } } } } return Result; } };

四、體會

這道題是3Sum的一種延伸,但需要轉化一種思路以降低計算復雜度。如果僅僅按照3Sum的延伸來做這道題的話,算法的空間復雜度會達到O(n^3),但是空間復雜度為O(1)。可以換一種思路,在排序之後,先計算後面兩個數的和,並用哈希表存儲起來,然後就將問題轉變為了3Ssum的問題,只不過計算出第三個數之後,還需要在哈希表中找到和滿足條件的第三個數和第四個數。

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved