我正在嘗試使用 Eclipse 做一個二和問題。我想使用一個數(shù)組并讓程序執(zhí)行標準遞歸以查看下面列出的數(shù)組中的任何整數(shù)是否可以加在一起等于我的目標總和 9。這是我正在解決的問題，在實施我的策略時遇到了麻煩......（注意我已經(jīng)嘗試過對我的編碼進行多種解釋）給定一個整數(shù)數(shù)組，返回兩個數(shù)字的索引，使它們加起來等于一個特定的目標。您可能會假設每個輸入只有一個解決方案，并且您可能不會兩次使用相同的元素。例子：給定 nums = [2, 7, 11, 15], target = 9,因為 nums[0] + nums[1] = 2 + 7 = 9，返回 [0, 1]。import java.util.ArrayList;public class twoSumArray { public twoSumArray(int[] nums, int target) { for(int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { } } } } public static void main(String[] args) { ArrayList<Integer>myArray = new ArrayList<Integer>(); myArray.add(2); myArray.add(7); myArray.add(11); myArray.add(15); int target = 9; ArrayList<Integer> result = twoSum(myArray,target); for(int j : result) System.out.print("["+j+","+target+"]"); }}我試過的另一個代碼......class Solution { public static int[] twoSum(int[] nums, int target) { for(int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return new int[] {i, j}; } } } System.out.println(twoSum.Solution); } public static void main(String[] args) { int[] nums = {2,7,11,15}; twoSum(nums , 9); }}
4 回答
MYYA
TA貢獻1868條經(jīng)驗 獲得超4個贊
您的代碼中存在一些語法錯誤。為了簡潔起見，我將發(fā)布一個您要實現(xiàn)的目標的最小示例。
沒有散列，你不會得到下面運行的答案O(n^2)
但是，您可以獲得 aO(n^2)而無需散列（您的第二個解決方案實際上在邏輯上是正確的，但在語法上是錯誤的。）例如，您為什么要打印System.out.println(twoSum.Solution);？你打電話twoSum(nums , 9);但你從來沒有真正打印結(jié)果。
public class TwoSum {
public static void main(String[] args) {
int[] answer = twoSum(new int[]{1, 2, 3}, 4);
if (answer != null)
System.out.println("[" + answer[0] + ", " + answer[1] + "]");
}
public static int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) return new int[]{ i, j };
}
}
// no answer
return null;
}
}
這個解決方案通常不受歡迎，因為它不是最有效的，而且是一種蠻力算法。但是，它非常簡單，不需要太多思考就可以理解。
料青山看我應如是
TA貢獻1772條經(jīng)驗 獲得超8個贊
您確實要求遞歸解決方案。所以這可行，但它確實需要為vals數(shù)組提供起始索引。
int[] vals = { 1, 2, 7, 9, 5, 3, 10};
System.out.println(Arrays.toString(twoSum(vals, 0, 1, 15)));
public static int[] twoSum(int[] v, int n, int m, int target) {
if (n == v.length) {
return new int[] { -1, -1
};
}
if (m == v.length) {
return twoSum(v, n + 1, n + 2, target);
}
if (v[n] + v[m] == target) {
return new int[] { n, m
};
}
return twoSum(v, n, m + 1, target);
}
[-1,-1]如果找不到總和，它會返回一個數(shù)組。您還可以返回一個空數(shù)組甚至null.
這應該很容易理解。它基本上像兩個嵌套循環(huán)一樣工作，遞增n并m適當?shù)貦z查invariants以確保索引不等于數(shù)組長度。
但是，如果您只想要一個行為完全相同的普通舊嵌套循環(huán)解決方案，您可以執(zhí)行以下操作：
public static int[] twoSum(int[] v, int target) {
for (int n = 0; n < v.length - 1; n++) {
for (int m = n + 1; m < v.length; m++) {
if (v[n] + v[m] == target) {
return new int[] { n, m
};
}
}
}
return new int[] { -1, -1
};
}
有只小跳蛙
TA貢獻1824條經(jīng)驗 獲得超8個贊
我意識到我遲到了這個討論 - 但是是的，你可以在線性時間內(nèi)解決“雙和”而不用散列（僅使用標準數(shù)組），前提是你的所有源值都是非負的（即使那樣，有一些巧妙的解決方法 - 請參閱此答案的底部）。
訣竅是聲明一個布爾數(shù)組，其容量等于源數(shù)組中的最大值（警告） *。或者，如果您想避免對數(shù)組進行額外的線性時間掃描以獲得其最大值，并且您不介意使用額外的空間，只需將容量設置為最大允許的數(shù)組容量（在我的語言中使用，C#，是2147483591）：
// Some test input data:
var target = 11;
var arr = new[] { 1, 2, 7, 9, 5, 3, 10 };
// complements array:
var complements = new bool[2147483591];
當數(shù)組聲明為容量時，其值將自動填充給定數(shù)據(jù)類型的默認值，對于布爾值是false.
現(xiàn)在只需單次遍歷源數(shù)組以查看數(shù)組中complements位置處的元素compIndex（即target減去當前數(shù)組元素）是否設置為true.
如果是這樣，將(num, compIndex)元組添加到結(jié)果集中。否則，將處的元素的值設置complements為。truenum
這是整個功能：
IEnumerable<(int, int)> TwoSum(int[] arr, int target)
{
var foundResults = new List<(int, int)>();
var complements = new bool[2147483591] // or arr.Max() but be careful of overflow;
foreach (var num in arr)
{
var compIndex = target - num;
if (complements[compIndex])
{
foundResults.Add((num, compIndex));
}
else
{
complements[num] = true;
}
}
return (foundResults.Any() ? foundResults : new[] { (-1, -1) });
}
void Main()
{
var target = 10;
var arr = new[] { 1, 2, 7, 9, 5, 3, 10 };
TwoSum(arr, target);
// returns [{9, 1},{3, 7}]
}
上面的 C# 代碼可以很容易地翻譯成 C、Java、JavaScript 等。
（警告） * 如果您的源數(shù)組包含的值大于布爾數(shù)組的最大容量，則有多種方法可以解決此問題（在 Google 上搜索與BigArray<T>您選擇的語言相關(guān)的實現(xiàn)）。同樣，如果您必須考慮源數(shù)組中的負數(shù)，也有創(chuàng)造性的方法來解決這個問題。例如，使您的complements布爾數(shù)組成為布爾2 元組數(shù)組而不是標量（即標記給定數(shù)字的正負版本是否存在的值）。
（請注意，在現(xiàn)實生活中，我會簡單地使用基于哈希的解決方案，而不是經(jīng)歷所有這些麻煩。但我已經(jīng)包含了這個答案，以防萬一您在與非常嚴格的招聘經(jīng)理的面試中遇到這個問題:-)）。
慕工程0101907
TA貢獻1887條經(jīng)驗 獲得超5個贊
您需要使用 gready 方式執(zhí)行此操作，您開始對最大（結(jié)果）以下的任何數(shù)字序列求和
每次選擇似乎是最佳選擇的數(shù)字（最佳選擇意味著它與前一個總和的總和不大于所需的結(jié)果）并且不重復地強制執(zhí)行此操作，直到您獲得所有可能的組合或使用回溯返回當你溢出結(jié)果并測試其他組合選項時的步驟數(shù)這比簡單的天真的野蠻力方法要快得多，如果我給你一個足夠大的數(shù)組，那將不得不測試 nlog(n) 組合那是不真實的
編輯：我注意到在評論后它添加了兩個數(shù)字而不是一個集合然后它更簡單首先蠻力天真的方法是最糟糕的因為除了操作等式中數(shù)字的位置并不重要所以你測試每個數(shù)字通過右邊的下一個數(shù)字直到 N-1 它的 N*2-1 可比較而不是 N^2 在 niave force
添加回答
舉報
0/150
提交
取消