-
Notifications
You must be signed in to change notification settings - Fork 0
/
two_sum.dart
57 lines (53 loc) · 1.5 KB
/
two_sum.dart
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/// Two Sum:
/// Topic: [Arrays, Hashing]
///
/// Statement: Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
///
/// Example:
/// ```dart
/// Input: nums = [2, 7, 11, 15], target = 9
/// Output: [0, 1]
///
/// Explanation: nums[0] + nums[1] = 2 + 7 = 9.
/// ```
void main() {
final nums = [2, 7, 11, 15, 5, 4];
final target = 9;
final targetIndices = getTargetIndices(nums, target);
print("this is target Indices with O(N)^2: $targetIndices");
final targetIndciesWithHashTable = getTargetIndicesWithHasTable(nums, target);
print("this is target Indices with O(N): $targetIndciesWithHashTable");
}
///BruteForce Approach
///
///In this way Time complexity would be O(n)^2;
List<(int, int)> getTargetIndices(
List<int> myArray,
int target,
) {
List<(int, int)> targetIndices = [];
for (int i = 0; i < myArray.length - 1; i++) {
for (int j = i + 1; j < myArray.length; j++) {
int sum = myArray[i] + myArray[j];
if (sum == target) {
targetIndices.add((i, j));
}
}
}
return targetIndices;
}
List<(int, int)> getTargetIndicesWithHasTable(
List<int> myArray,
int target,
) {
Map<int, int> myHasTable = {};
List<(int, int)> targetIndices = [];
for (int i = 0; i < myArray.length; i++) {
final result = target - myArray[i];
if (myHasTable.containsKey(result)) {
targetIndices.add((i, myHasTable[result]!));
}
myHasTable[myArray[i]] = i;
}
return targetIndices;
}