学会滑动窗口技术提高解题效率

骑猪看日落 2023-10-13 15:45 35阅读 0赞

#### 文章目录 ####

*  理解滑动窗口技术
 *  效率优势
 *  用例1：银行应用
 *  用例2：欺诈检测 - 异常检测
 *  用例3： 最长子字符串

![在这里插入图片描述][74b11483a33e4faca7a334f772ecad05.png]

## 理解滑动窗口技术 ##

滑动窗口技术涉及在数据结构中维护一个元素的“窗口”，并通过迭代滑动窗口来高效解决特定问题。通过优化数据处理方式，我们通常可以实现比蛮力方法更好的时间复杂度。

## 效率优势 ##

1.  减少计算量：滑动窗口技术通过重用窗口内先前计算的结果来避免不必要的重复计算。这导致了改进的时间复杂度和更快的执行速度。
2.  线性复杂度：在许多情况下，滑动窗口技术使我们能够以线性时间复杂度（O(n)）解决问题，这比二次或指数复杂度更高效。

## 用例1：银行应用 ##

考虑一个需要识别连续交易金额超过一定阈值的最长序列的银行应用。滑动窗口技术非常适合这种情况。通过维护一个交易金额窗口并将其滑动到数据中，我们可以高效地识别出最长的序列，而无需检查每个可能的子数组。

让我们看一个JavaScript实现这个用例的滑动窗口技术的例子：

function findLongestSequence(transactions, threshold) {
        
      let maxLength = 0;
      let currentLength = 0;
    
      for (let i = 0; i < transactions.length; i++) {
        
        if (transactions[i] > threshold) {
        
          currentLength++;
        } else {
        
          maxLength = Math.max(maxLength, currentLength);
          currentLength = 0;
        }
      }
    
      return Math.max(maxLength, currentLength);
    }
    
    // 示例用法：
    const transactions = [120, 140, 200, 80, 100, 250, 300, 320, 200, 180];
    const threshold = 150;
    const longestSequence = findLongestSequence(transactions, threshold);
    console.log(`超过${
          threshold}的最长序列：${
          longestSequence}`);

在这个例子中，我们定义了一个函数，该函数接受一个交易数组和一个阈值金额。函数遍历交易数组，维护连续金额超过阈值的当前长度。当交易金额低于阈值时，将当前长度与迄今为止遇到的最大长度进行比较。最后，函数返回最长序列的长度。

## 用例2：欺诈检测 - 异常检测 ##

在银行交易中检测异常和潜在欺诈非常重要。滑动窗口技术可用于识别交易金额中的异常模式。

function detectAnomalies(transactions, windowSize, threshold) {
        
      const anomalies = [];
    
      for (let i = 0; i < transactions.length; i++) {
        
        if (i >= windowSize) {
        
          const window = transactions.slice(i - windowSize, i);
          const average = window.reduce((sum, amount) => sum + amount, 0) / windowSize;
    
          if (transactions[i] > threshold * average) {
        
            anomalies.push({
         transaction: transactions[i], index: i });
          }
        }
      }
    
      return anomalies;
    }
    
    // 示例用法：
    const transactionAmounts = [100, 150, 200, 120, 180, 900, 120, 250, 300, 80];
    const windowSize = 5;
    const anomalyThreshold = 2;
    const detectedAnomalies = detectAnomalies(transactionAmounts, windowSize, anomalyThreshold);
    console.log('检测到的异常：', detectedAnomalies);

在这个例子中，我们通过将每个交易与先前窗口的平均值进行比较，来检测交易金额中的异常。如果交易金额超过了某个阈值（例如平均值的两倍），则将其标记为异常。通过使用滑动窗口，我们可以高效地分析交易模式并识别潜在的欺诈。

## 用例3： 最长子字符串 ##

具有K个不同字符的最长子字符串。给定一个字符串，您可以使用滑动窗口技术找到包含最多K个不同字符的最长子字符串的长度。

function findLongestSubstringWithKDistinct(str, k) {
        
      let longestLength = 0;
      let start = 0;
      const charMap = new Map();
    
      for (let end = 0; end < str.length; end++) {
        
        const currentChar = str[end];
        charMap.set(currentChar, (charMap.get(currentChar) || 0) + 1);
    
        while (charMap.size > k) {
        
          const leftChar = str[start];
          charMap.set(leftChar, charMap.get(leftChar) - 1);
          if (charMap.get(leftChar) === 0) {
        
            charMap.delete(leftChar);
          }
          start++;
        }
    
        longestLength = Math.max(longestLength, end - start + 1);
      }
    
      return longestLength;
    }
    
    // 示例用法：
    const inputString = 'aabacbebebe';
    const k = 3;
    const longestLength = findLongestSubstringWithKDistinct(inputString, k);
    console.log(`包含${
          k}个不同字符的最长子字符串的长度：${
          longestLength}`);

[74b11483a33e4faca7a334f772ecad05.png]: https://img-blog.csdnimg.cn/74b11483a33e4faca7a334f772ecad05.png

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关学会滑动窗口技术提高解题效率

文章目录理解滑动窗口技术效率优势用例1：银行应用用例2：欺诈检测 - 异常检测用例3：最长子字符串 ![在这里插入图片描

骑猪看日落/ 2023年10月13日 15:45/ 0 赞/ 36 阅读

相关【独家】华为OD机试 - 滑动窗口（C 语言解题）

最近更新的博客 [华为od 2023 | 什么是华为od，od 薪资待遇，od机试题清单][od 2023 _ _od_od _od] [华为OD机试真题大全

柔光的暖阳◎/ 2023年09月29日 22:00/ 0 赞/ 44 阅读

相关 leetcode 解题启发 --滑动窗口

滑动窗口的应用广泛，常用于减少线性逻辑的时间复杂度问题上。滑动窗口思想：在线性逻辑中，允许用单位长度方向性的移动，通过计算窗口的值，求解最终值滑动窗口特点：依

阳光穿透心脏的1/2处/ 2023年05月31日 03:16/ 0 赞/ 22 阅读

相关 LeetCode常见解题思路——滑动窗口

LeetCode常见解题思路——滑动窗口思路说明输入：一个数组或者是字符串求解问题的共性：子数组或子字符串具有某种特性的算法思想通过窗

水深无声/ 2022年11月08日 11:57/ 0 赞/ 200 阅读

相关 LeetCode 滑动窗口最大值【滑动窗口】

1 滑动窗口最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移

秒速五厘米/ 2022年09月10日 11:26/ 0 赞/ 238 阅读

相关学会使用代码片段提高编程效率

Table of Contents 1. 使用代码片段提高编程效率 1. UltiSnips is the ultimate solution fo

╰半夏微凉°/ 2022年09月04日 10:53/ 0 赞/ 198 阅读

相关 leetcode滑动窗口

1. 无重复字符的最长子串给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。输入: s = “abcabcbb” 输出: 3 采用滑动窗口搜

Bertha 。/ 2022年09月04日 09:53/ 0 赞/ 270 阅读

相关 Unity 滑动窗口

unity 滑动窗口创建一个image 名为Note 在Note下再创建一个image image下创建一个text ![Center][] 调节大小比如N

不念不忘少年蓝@/ 2022年06月14日 01:47/ 0 赞/ 264 阅读

相关滑动窗口

①初始态，发送方没有帧发出，发送窗口前后沿相重合。接收方0号窗口打开，等待接收0号帧； ②发送方打开0号窗口，表示已发出0帧但尚确认返回信息。此时接收窗口状态不变； ③发送

喜欢ヅ旅行/ 2022年03月15日 07:12/ 0 赞/ 320 阅读

相关滑动窗口技术

leetcode3.209等题目都是滑动窗口解决的。都是一种在数组这种数据结构中寻找最长，最短的情况，咋一看刚开始想着动态规划可能是这种题目的解法。但是适用于动态规

ゝ一纸荒年。/ 2022年02月01日 14:19/ 0 赞/ 299 阅读