我正在嘗試解決 GeeksClasses 中的問(wèn)題，但我的提交有問(wèn)題。我的代碼有效，但他們說(shuō)您的程序花費(fèi)的時(shí)間比預(yù)期的要多。問(wèn)題鏈接： https ://practice.geeksforgeeks.org/problems/find-triplets-with-zero-sum/1/?track=SPCF-Sorting&batchId=154問(wèn)題陳述：給定一個(gè)整數(shù)數(shù)組。檢查它是否包含總和為零的三元組。輸入：輸入的第一行包含一個(gè)整數(shù)T，表示測(cè)試用例的數(shù)量。然后是 T 個(gè)測(cè)試用例。每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù) N，表示數(shù)組中元素的數(shù)量。每個(gè)測(cè)試用例的第二行包含數(shù)組的 N 個(gè)空格分隔值。輸出對(duì)于每個(gè)測(cè)試用例，如果存在三元組，則輸出為 1，否則為 0預(yù)期輔助空間：O(1)預(yù)期時(shí)間復(fù)雜度：O(n2)例子：輸入：250 -1 2 -3 131 2 3輸出：10這是我的代碼def isPair(arr,left,right,u): while left < right: if arr[left] + arr[right] < u: left += 1 elif arr[left] + arr[right] == u: return True elif arr[left] + arr[right] > u: right -= 1 return Falsedef findTriplets(a,n): #code here a = sorted(a) for i in range(n): if isPair(a,i+1,n-1,0-a[i]): return 1 return 0#driver codeif __name__=='__main__': t=int(input()) for i in range(t): n=int(input()) a=list(map(int,input().strip().split())) print(findTriplets(a,n))
2 回答
慕少森
TA貢獻(xiàn)2019條經(jīng)驗(yàn) 獲得超9個(gè)贊
這個(gè)問(wèn)題看起來(lái)很有趣，這里有兩個(gè)我們可以使用的觀察結(jié)果。每個(gè)有效的三元組都是以下任一形式：
(0, -x, x)
或 (x, y, z) 使得 x 和 y 與 z 的符號(hào)相反并且 x + y = - z
我會(huì)考慮一種更簡(jiǎn)單的輸入形式，因?yàn)槟拇蟛糠州斎雽?duì)于兩個(gè)整數(shù)列表的內(nèi)容都是多余的，即。example_1 = [[0, -1, 2, -3, 1], [1, 2, 3]]應(yīng)該導(dǎo)致[1, 0].
鑒于我認(rèn)為以下是一個(gè)相當(dāng)快速/可讀的解決方案：
from itertools import combinations
def solve_all(inputs):
return [solve(i) for i in inputs]
def solve(single_input):
input_set = set(single_input)
negatives_set = set(-x for x in single_input if x < 0)
positives_set = set(x for x in single_input if x > 0)
if 0 in input_set and len(negatives_set & positives_set) > 0:
return 1
if any(sum(c) in positives_set for c in combinations(negatives_set, 2)):
return 1
if any(sum(c) in negatives_set for c in combinations(positives_set, 2)):
return 1
return 0
白衣非少年
TA貢獻(xiàn)1155條經(jīng)驗(yàn) 獲得超0個(gè)贊
public class FindTriplets{
public static List<List<Integer>> findTriplets(int nums[]) {
boolean found = false;
List<Integer> triples = null;
HashSet<Integer> set = null;
HashSet<List<Integer>> tripleSet = new HashSet<List<Integer>>();
for (int i = 0; i < nums.length - 1; i++) {
set = new HashSet<Integer>();
for (int j = i + 1; j < nums.length; j++) {
found = false;
int x = -(nums[i] + nums[j]);
if (set.contains(x)) {
Integer [] temp = {x,nums[i],nums[j]};
Arrays.sort(temp);
triples = new ArrayList<Integer>();
triples.add(temp[0]);
triples.add(temp[1]);
triples.add(temp[2]);
found = true;
} else {
set.add(nums[j]);
}
if(found==true){
tripleSet.add(triples);
}
}
}
return new ArrayList<List<Integer>>(tripleSet);
}
public static void main(String[] args) {
int arr[] = {0, -1, 2, -3, 1};
//int arr[] = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> triplets = findTriplets(arr);
System.out.println("Triplets : "+triplets );
}
}
添加回答
舉報(bào)
0/150
提交
取消