在一个升序数组中已知一个目标数,找到所有相加(可能是2个相加,3个相加或是四个相加)等于这个数的index c语言实现
时间: 2023-06-19 20:07:44 浏览: 57
这道题可以使用双指针的方法来解决。具体思路如下:
1. 对于每一个数,将其作为第一个加数,然后在剩余的数中寻找第二个加数,如果找到了,则输出两个加数的 index。
2. 对于每一对加数,将它们的和作为第一个加数,然后在剩余的数中寻找第二个加数,如果找到了,则输出三个加数的 index。
3. 对于每一组三个加数,将它们的和作为第一个加数,然后在剩余的数中寻找第二个加数,如果找到了,则输出四个加数的 index。
代码实现如下:
```
void findSum(int arr[], int n, int target) {
int i, j, k, l;
for (i = 0; i < n - 3; i++) {
for (j = i + 1; j < n - 2; j++) {
for (k = j + 1; k < n - 1; k++) {
for (l = k + 1; l < n; l++) {
if (arr[i] + arr[j] + arr[k] + arr[l] == target) {
printf("Found 4 numbers with target sum at index %d, %d, %d, %d\n", i, j, k, l);
}
}
}
}
}
for (i = 0; i < n - 2; i++) {
for (j = i + 1; j < n - 1; j++) {
for (k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == target) {
printf("Found 3 numbers with target sum at index %d, %d, %d\n", i, j, k);
}
}
}
}
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
printf("Found 2 numbers with target sum at index %d, %d\n", i, j);
}
}
}
}
```
这个算法的时间复杂度是 O(n^4),不是很高效。如果数组中的数比较大,可以考虑先将数组排序,然后再使用双指针进行查找,这样时间复杂度可以降到 O(n^3) 或者 O(n^2)。