在一个严格递增的整数数组(含有n个元素)里找到两个数，使得他们的和等于给定值，假设有且仅有一对解。输入是一个数组和一个给定值，要求输出两个数的位置，从下标1开始计数。 要求：算法时间复杂程度O(n)。

可以使用双指针法来解决这个问题。定义两个指针left和right，分别指向数组的第一个和最后一个元素。然后比较left和right指向的元素之和与给定值的大小关系，如果和小于给定值，则将left指针右移一位；如果和大于给定值，则将right指针左移一位；如果和等于给定值，则找到了一对解，返回它们的位置。

具体实现如下：

public int[] findTwoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left+1, right+1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return null;
}

时间复杂度为O(n)，因为双指针最多遍历整个数组一次。

相关问题

给定一个整数数组nums，找到其中最长严格递增子序列的长度c语言简单

给定一个整数数组 `nums`，寻找其中最长的严格递增子序列的长度，你可以使用动态规划算法来解决这个问题。动态规划是一种常见的优化策略，特别适合这类涉及最优化子问题的问题。

以下是一个简单的C语言函数实现：

#include <stdio.h>

int lengthOfLIS(int* nums, int n) {
    // 初始化一个长度为n+1的一维数组dp，存储每个位置到结尾的最大严格递增子序列长度
    int dp[n + 1];
    dp[0] = 1; // 空序列本身就是递增的

    // 遍历输入数组
    for (int i = 1; i <= n; i++) {
        // 对于每一个元素，尝试将它添加到已知的递增序列的末尾
        // 如果新序列比当前dp[i]值大，更新dp[i]为当前元素加上对应元素之前的最长递增子序列长度
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 最终dp数组的最后一个元素就是所求最长递增子序列的长度
    return dp[n];
}

// 使用max函数，这里假设已经定义了比较两个整数大小的函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(nums) / sizeof(nums[0]);
    int longestLength = lengthOfLIS(nums, n);
    printf("The length of the longest increasing subsequence is %d.\n", longestLength);
    return 0;
}

一个整数序列，找到一个该序列中的最长严格递增子序列，使得子序列中任意两个相邻元素的差的绝对值都不低于给定的阈值d，输出该子序列及其长度。给我一个c语言代码

在C语言中，你可以使用动态规划的方法来解决这个问题。这里是一个简单的算法示例，它使用了Kadane's Algorithm（ Kadane's 算法），这是一种用于寻找数组中连续子数组最大和的经典动态规划技术，稍作修改即可适应于这个特定问题。

#include <stdio.h>
#include <stdlib.h>

// 函数声明
int longest_increasing_subsequence(int* arr, int n, int d);

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;
    int result_len, *subsequence;

    // 计算最长子序列长度及子序列
    result_len = longest_increasing_subsequence(arr, n, d);
    subsequence = (int*)malloc(result_len * sizeof(int));

    printf("Longest increasing subsequence with minimum difference of %d is: ", d);
    for (int i = 0; i < result_len; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\nLength: %d\n", result_len);

    free(subsequence);  // 别忘了释放内存
    return 0;
}

// 动态规划函数
int longest_increasing_subsequence(int* arr, int n, int d) {
    int dp[n];  // dp 数组，存储以每个元素结尾的最大子序列长度
    int maxLength = 0;  // 最大子序列长度
    int endIndex = -1;  // 子序列结束的最后一个元素索引

    for (int i = 0; i < n; ++i) {
        dp[i] = 1;  // 初始化所有元素的子序列长度为1
        
        // 检查以当前元素结尾是否能得到更长的子序列
        for (int j = 0; j < i; ++j) {
            if (abs(arr[j] - arr[i]) >= d && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                if (dp[i] > maxLength) {
                    maxLength = dp[i];
                    endIndex = i;
                }
            }
        }
    }

    // 从原始数组构建最长子序列
    int* longestSubseq = (int*)malloc(maxLength * sizeof(int));
    longestSubseq[maxLength - 1] = arr[endIndex];
    int prevEnd = endIndex;
    for (int i = maxLength - 2; i >= 0; --i) {
        while (arr[prevEnd - 1] - arr[endIndex] >= d && prevEnd != 0) {
            prevEnd--;
        }
        longestSubseq[i] = arr[prevEnd];
    }

    return maxLength;
}

在这个代码中，`longest_increasing_subsequence` 函数计算出满足条件的最长子序列，并在主函数中打印结果。注意，这个代码只适用于正序查找，如果输入数组可能包含负数或其他顺序，需要对代码进行相应调整。同时，`longestSubseq` 的构建部分假设了递减的子序列是从当前元素开始的最短递增子序列，这取决于问题的具体定义。如果你的问题描述有所不同，这部分也可能需要修改。